题目描述

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示：

• intervals[i][0] <= intervals[i][1]

算法

直接上算法

• 首先对二维数组中的元素排序，对于[1,3]和[2,6]两个元素，排序的规则是谁的第一个元素小，谁就在前面，当第一个元素相同时，谁的第二个元素小谁就在前面
• 对整个二维数组排好序以后，我们定义快慢两个指针slow和fast，然后比较他们两个指针指向的值是否需要合并
  • 如果不需要合并，那么就将当前slow指向的值存入结果中，并且将slow重定向指向fast，然后将fast向后移动一位
  • 如果需要合并，那么就合并，合并以后slow不变，fast向后移动一位
• 合并的方式是通过比较slow和fast指向的值，然后直接在slow指向的值上面做出修改

代码如下

type slices [][]int
func (s slices) Len() int {
	return len(s)
}
func (s slices) Less(i, j int) bool {
	if s[i][0] <= s[j][0] {
		if s[i][0] == s[j][0] {
			if s[i][1] <= s[j][1] {
				return true
			}
		}
		return true
	}
	return false
}
func (s slices) Swap(i, j int) {
	s[i][0], s[i][1], s[j][0], s[j][1] = s[j][0], s[j][1], s[i][0], s[i][1]
}
func merge(intervals [][]int) [][]int {
	res := make([][]int, 0)
	if len(intervals) == 0 {
		return res
	}
	if len(intervals) == 1 {
		return intervals
	}
	sort.Sort(slices(intervals))
	// flag:=false
	slow, fast := 0, 1
	for fast != len(intervals) {
		// 如果不需要合并，那么slow和fast都向后移一步，并且将当前的slow存入res
		if intervals[slow][1] < intervals[fast][0] {
			res = append(res, intervals[slow])
			slow = fast
			fast++
		} else {
			// 需要合并，那么就合并，并且slow不动，fast向后移动一步
			var bigger int
			if intervals[slow][1] >= intervals[fast][1] {
				bigger = intervals[slow][1]
			} else {
				bigger = intervals[fast][1]
			}
			intervals[slow][1] = bigger
			fast++
		}
		if fast == len(intervals) {
			res = append(res, intervals[slow])
		}
	}
	return res
}