代码随想录贪心算法——合并区间

题目

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

示例 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]表示区间i的左边界 ，intervals[i][1]表示区间i的右边界。

根据左边界从小到大排序之后，如果intervals[i][0] < intervals[i-1][1]，即当前区间intervals[i] 的左边界 < 上一个区间intervals[i-1]的右边界，则一定有重叠，因为intervals[i]的左边界一定是大于等于intervals[i-1]的左边界（因为已经按照左边界进行排序了）

即：intervals[i]的左边界[0]在intevals[i-1]的左边界[0]和右边界[1]的范围之内，那么一定有重叠部分，即intervals[i][0] < intervals[i-1][1]

在判断重叠之后，就是要进行区间合并， 相当于就是用前一个区间的左边界和当前区间的右边界组成一个新的区间加入到数组result中，如果没有合并就把原区间加入result数组即可

算法核心思想：

先排序，再比较；将数组按照左边界start进行排序，然后比较前一个区间的右边和后一个区间的左边（即start），有重合就重新定义end，没有重合就将原区间加到链表里，最后将链表转换成数组

java代码如下：

class Solution {
	public int[][] merge(int[][] intervals){
		List<int[]> result = new LinkedList<>();//ArrayList也可以
		//按照左边界排序
		Arrays.sort(intervals, (x,y) -> Integer.compare(x[0],y[0]));//即intervals[x]表示第x个区间，intervals[x][0]表示第x个区间的左边界，这里排序是区间x和区间y，分别去比较x[0]和y[0]，x[0]表示区间x的左边界，y[0]表示区间y的左边界
		//另一种写法也可以
		//Arrays.sort(intervals, (x,y) -> (x[0] - y[0]));但是没有Integer.compare(x[0],y[0])好
		int left = intervals[0][0];//初始化左边界
		int right = intervals[0][1];//初始化右边界
		for(int i = 1; i < intervals.length; i++){
			if(intervals[i][0] <= right){//如果区间有重合，即当前区间左边界小于上一个区间的右边界,在这个for循环中最开始循环相当于就是intervals[i][0]和 intervals[0][1]进行比较
				if(intervals[i][1] > right){//进行合并操作，如果当前区间右边界大于前一个区间右边界，则更新新的右边界值
					right = intervals[i][1];
				}
			} else {//如果区间没有重合，则直接加入原区间
				result.add(new int[]{left, right});//将[left,right]加入reslut数组中
				//更新区间的左右边界
				left = intervals[i][0];
				right = intervals[i][1];
			}
		}
		result.add(new int[]{left,right});//把最后一个区间加上
        return result.toArray(new int[result.size()][2]);//将链表result转化成二维数组，其中result.size表示有几个区间，2表示区间有2个值
	}
}
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