每日一练：LeeCode-56、合并区间【数组+滑动窗口】

4.合并区间

LeeCode-56、合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

思路：

1、对二维数组按照第一列升序排序
2、进行合并数组

• int term[] =intervals[0]，作为临时空间，判断是否需要合并集合和是否放入结果集
• 若上一个数组的右边值>=下一个数组的左边值，则比较两个数组右边的值
• 若上一个数组的右边值<下一个数组的左边值,则将上一个数组放进列表中，下一个数组接力，如果是最后一个数组，则直接加进去即可
• 最后一个也要加入，否则会漏掉

class Solution {
 public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return intervals;
       //1、对二维数组按照第一列升序排序
       Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
      //2、进行合并数组
      List<int []> list = new ArrayList<>();
      int term[] =intervals[0]; //临时空间，1 判断是否需要合并集合，2 是否放入结果集
     //term[0]=最左边的，term[1]：动态的右边，循环直到右边小于其它的左边任何数，才停止，并加入list
     for (int i = 1; i < intervals.length; i++) {
         if (term[1]>=intervals[i][0]){      //上一个数组的右边值>=下一个数组的左边值
             term[1]=Math.max(term[1],intervals[i][1]);   //比较两个数组右边的值
         }else {
             list.add(term);        //将上一个数组放进列表中
             term=intervals[i];    //下一个数组接力，如果是最后一个数组，则直接加进去即可
         }
     }
     list.add(term);   //最后一个
     return list.toArray(new int[list.size()][2]);//列表转化成数组，并必须进行数据初始化
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21