56. Merge Intervals合并区间

• 题目描述
• 思路
• 实现

题目描述

Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

思路

1. 先按每个区间第一个元素进行升序排序：使用lambda函数

2. 创建一个list来存放得到的合并区间（最后再转换成二维数组）

3. 再遍历所有区间，比较当前遍历的区间的结尾和下一个区间的开头：
   若当前结尾>=下一个开头：需要覆盖区间，得到的合并区间结尾是两个区间中结尾更大的那个
   若当前结尾<下一个开头：不需要覆盖区间，直接把当前遍历到的区间加入list

4. 最终把list转换成二维数组，并返回该二维数组

实现

public int[][] merge(int[][] intervals) {
        //特殊情况：没有区间或只有一个区间，不需要合并
        if(intervals.length<2) return intervals;
        
        
        //先按每个区间第一个元素进行升序排序：使用lambda函数
        Arrays.sort(intervals,(i1,i2)->Integer.compare(i1[0],i2[0]));
        
        //先用list存放合并的区间（最后转换成二维数组）
        List<int[]> res = new ArrayList<>();
        //newInterval是对比当前区间结尾和下一个区间开头后，合并得到的区间（初始是第一个区间）
        int[] newInterval = intervals[0];   
		res.add(newInterval);     //第一个区间不需要合并，直接放进list
		
        //遍历所有区间，比较当前区间结尾和下一区间开头，判断是否需要合并
          //简单遍历法
		for (int[] interval : intervals) {    //interval[i]代表第i+1个区间
			if (interval[0] <= newInterval[1]) // 若后一个区间的开头<=当前区间的结尾，覆盖区间（0下标代表区间开头，1代表结尾）
				newInterval[1] = Math.max(newInterval[1], interval[1]);
			else {                             // 若后一个区间开头>当前区间结尾，不需要覆盖，直接把当前区间加入到List
				newInterval = interval;   
				res.add(newInterval);
			}
      }
        return res.toArray(new int[res.size()][]); //list转换成二维数组
    }