LeetCode刷题-重叠区间问题

跟着甜姨整理了这一类问题，没有固定套路，但需要找规律以及细心。

重叠区间

252，会议室，easy

题解

实质是判断有没有重叠区间，将区间按照会议开始时间排序，然后遍历一遍即可。

代码

class Solution{
    public boolean canAttendMeetings(int[][] intervals){
        Arrays.sort(intervals, (v1, v2)->v1[0]-v2[0]);
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] < intervals[i - 1][1])
                return false;
        }
        return true;
    }
}

56，合并区间，medium

题解

与上一题的区别在于要合并重叠的区间，还是从intervals的第一个元素开始遍历，最开始比较的对象为intervals[0][1]，在遍历过程中不断更新，此对象的含义为上一个区间的末尾。即新的区间的开头比上一区间的末尾大，就不需要合并。

代码

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 1) return intervals;
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        int flag = intervals[0][1];
        int[][] res = new int[intervals.length + 1][2];
        int idx = 0;
        res[0] = intervals[0];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] <= flag){
                res[idx][1] = Math.max(res[idx][1], intervals[i][1]);
                flag = res[idx][1];
            }else{
                res[++idx] = intervals[i];
                flag = intervals[i][1];
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }
}

57，插入区间，medium

题解

本题中的区间已经按照起始端点升序排列，因此我们直接遍历区间列表，寻找新区间的插入位置即可。具体步骤如下：

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

代码

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int pL = newInterval[0];
        int pR = newInterval[1];
        int[][] res = new int[intervals.length + 1][2];
        int i = 0;
        //[[1,2],[3,5],[6,7],[8,10],[12,16]]
        //         4          8
        //[[1,2],[3,10],[12,16]]	
        int idx = 0;
        //无重叠部分
        while(i < intervals.length && intervals[i][1] < pL){
            res[idx++] = intervals[i++];
        }
        // 接着判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，
        // 将最终合并后的新区间加入结果集 
        while(i < intervals.length && intervals[i][0] <= pR){
            pL = Math.min(intervals[i][0], pL);
            pR = Math.max(intervals[i][1], pR);
            i++;
        }
        res[idx++] = new int[]{pL, pR};
        while(i < intervals.length){
            res[idx++] = intervals[i++];
        }
        return Arrays.copyOf(res, idx);
    }
}

1288，删除被覆盖区间，medium

题解

贪心

先按区间左边界升序排列，如果相等，按右区间降序排列（消除覆盖区间）

这样只需要更新一个右边界值即可

遍历区间，如果被覆盖，区间数-1；如果没有被覆盖，则更新新的边界值。

代码

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        if(intervals.length == 1) return 1;
        Arrays.sort(intervals, (v1, v2) -> v1[0] == v2[0] ? v2[1] - v1[1] : v1[0] - v2[0]);
   
        int res = intervals.length;
        int r = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][1] <= r){
                res--;
            }
            else r = Math.max(r, intervals[i][1]);
            
        }
        return res;
    }
}

228，汇总区间，easy

题解

对连续的数字按固定格式输出，那么双指针找到不连续的数字即可。

找到之后更新i = j + 1。

在一个循环中判断一下双指针所指位置，如果相同则只添加一个元素。

代码

class Solution {
    public List<String> summaryRanges(int[] nums) {
        //双指针
        List<String> res = new ArrayList<>();
        if(nums.length == 0) return res;
        if(nums.length == 1){
            res.add(String.valueOf(nums[0]));
            return res;
        }
        int i = 0;
        for(int j = 0; j < nums.length; j++){
            //找到第一个不符合递增规则的，或者遍历完成
            if(j == nums.length - 1 || nums[j] + 1 != nums[j + 1]){
                String tmp = String.valueOf(nums[i]) + "->" + String.valueOf(nums[j]);
                if(nums[i] != nums[j])
                    res.add(tmp);
                else res.add(String.valueOf(nums[j]));
                i = j + 1;
            }
            
        }
        return res;
    }
}