合并区间56

Algorithm 评论

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

示例 1:

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

示例 2:

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

思路:

  1. 怎么判断重叠: 两区间的最小的右边界 大于或等于 两区间最大的左边界. 如[1,5]和[2,8]
  2. 入参是切片的切片(intervals), 拿intervals[0]与它后面的所有区间对比, 从intervals[1]开始, 如果有与之重叠的区间, 就把合并后的新区间赋给intervals[0], 并删除参与合并的那个旧区间
  3. intervals[0]完成后, 拿``intervals[1]与它后边的所有区间对比, 从intervals[2]开始, 如果有与之重叠的区间, 就把合并后的新区间赋给intervals[1]`, 并删除参与合并的那个就区间
  4. 拿intervals[i] 与它后边的所有区间对比, 从intervals[i+1] 开始, 如果有与之重叠的区间intervals[j] , 就把合并后的新区间赋给 intervals[i] , 并删除参与合并的intervals[j]
  5. 如果第3步出现了有重叠的区间intervals[j], 那么合并后i 的值变了, 就有可能由原来 在i 到j 之间没有重叠的区间 变成 有重叠的区间, 所以需要从头(i+1) 再遍历一次, 直到再也没有重叠的区间
  6. 重复, 一直到切片末尾

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func merge(intervals [][]int) [][]int {

	for i := 0; i < len(intervals); {
		merged := false
		for j := i + 1; j < len(intervals); j++ {
			x, y := intervals[i], intervals[j]
			
			if min(x[1], y[1]) >= max(x[0], y[0]) {
				merged = true
				//重新赋值
				intervals[i][0], intervals[i][1] = min(x[0], y[0]), max(x[1], y[1])
				
				//删除j
				intervals[j] = intervals[len(intervals) - 1]
				intervals = intervals[:len(intervals) - 1]
			}
		}
		
		if merged {
			continue
		}
		i++
	}
	
	return intervals
}