算法通关村——盘点面试大热门之区间问题

1. 区间是否重叠？

LeetCode252.给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。

示例 1
输入: intervals = [[0,30],[15,20],[5,10]]
解释: 存在重叠区间，一个人在同一时刻只能参加一个会议。

1.1 贪心算法

只要数组里面的元素都是按照从小到大的顺序排列，那么只需要当前数组的第一个数大于前一个数组的第二个数，才能开始会议，否则直接退出

    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]<intervals[i-1][1]){
                return false;
            }
        }
        return true;
    }
1
2
3
4
5
6
7
8
9

2. 合并区间

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

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

合并区间

2.1 贪心算法

肯定是要开辟一个新的数组来存放相应的元素的，主要思路就是比较第一个数组的第二个元素和第二个数组的第一个元素，如果小于，就直接放入新数组，否则就比较第一个的第二个元素和第二个数组的第二个元素哪个大，然后合并区间。还需要采用一个下标作为新数组移动的标志。

public int[][] merge(int[][] intervals) {
         // 排序
         Arrays.sort(intervals,(v1,v2)->v1[0]-v2[0]);
         // 新数组
         int [][] res = new int[intervals.length][2];
         // 下标
         int idx =-1;
         for(int [] interval:intervals){
            //不合并，当前区间加入数组
            if(idx ==-1 || interval[0] > res[idx][1]){
                res[++idx] = interval;
            }else{
                // 合并区间
                res[idx][1] = Math.max(res[idx][1],interval[1]);
            }
         }
         // 合并数组区间
         return Arrays.copyOf(res,idx+1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. 插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）
示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
插入区间

3.1 贪心算法

总体思路就是上一题的拓展。
1.首先将新区间左边且相离的区间加入结果集（遍历时，如果当前区间的结束位置小于新区间的开始位置，说明当前区间在新区间的左边且相离）；
2.接着判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，将最终合并后的新区间加入结果集；
3.最后将新区间右边且相离的区间加入结果集。

    public int[][] insert(int[][] intervals, int[] newInterval) {
        int [][] res = new int[intervals.length+1][2];
        // 下标
        int idx = 0;
        int i= 0;
        // 添加数组的第一个元素大于区间数组的第二个元素，加入新区间数组
        while(i<intervals.length && intervals[i][1] <newInterval[0]){
            res[idx++] = intervals[i++];
        }
        // 区间数组的第一个元素小于添加数组的第一个元素，判断是否区间重叠。
        while(i<intervals.length && intervals[i][0]<=newInterval[1]){
            newInterval[0] = Math.min(intervals[i][0],newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1],newInterval[1]);
            i++;
        }

        res[idx++] = newInterval;

        // 添加剩余元素
        while(i<intervals.length){
            res[idx++] = intervals[i++];
        }

        return Arrays.copyOf(res,idx);
    }
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