LeetCode 57. 插入区间

57. 插入区间

 

 

【有序集合+区间合并】将所有区间放入一个有序集合中，按照左端点排序，对于新区间new[start, end]，寻找第一个左端点<=end的区间（floor方法），判断这个区间的右端点是否>=start，如果是就合并（合并方法其实就是取new和这个区间左端点的较小值，右端点的较大值），并删除掉原来的区间，然后继续寻找下一个符合条件能合并的区间，直到所有在覆盖范围内的区间都被合并起来。退出while循环后将最新的[start, end]加入集合即可。

class Solution {

    // 有序集合 11:52 12:05

    public int[][] insert(int[][] intervals, int[] newInterval) {
        TreeSet<int[]> set = new TreeSet<int[]>((a, b) -> {return a[0] - b[0];});
        for(var it: intervals) set.add(it);
        int start = newInterval[0], end = newInterval[1];
        int[] key = set.floor(new int[] {end, end});
        while(key != null){
            if(key[1] < start) break;
            start = Math.min(start, key[0]);
            end = Math.max(end, key[1]);
            set.remove(key);
            key = set.floor(new int[] {end, end});
        }
        set.add(new int[] {start, end});
        int[][] ans = new int[set.size()][];
        int i = 0;
        for(var k: set){
            ans[i++] = k;
        }
        return ans;
    }
}

【二分+区间合并】 突然发现区间已经有序，所以不用再开TreeSet了（其实用TreeSet）主要为了用他的floor方法，可以直接用二分来查，然后找到下标后继续往前找下标就行了。

class Solution {

    // 二分 10:00 10:19

    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start = newInterval[0], end = newInterval[1];
        int n = intervals.length, left = 0, right = n - 1;
        while(left <= right){
            int mid = (left + right) >>> 1;
            if(intervals[mid][0] > end) right = mid - 1;
            else left = mid + 1;
        }
        int idx = right;
        if(idx < 0){
            int[][] ans = new int[n + 1][];
            ans[0] = newInterval;
            int i = 1;
            for(var it: intervals) ans[i++] = it; 
            return ans;
        }
        else{
            int t = 0;
            while(true && idx >= 0){
                left = intervals[idx][0];
                right = intervals[idx][1];
                if(right < start) break;
                intervals[idx][0] = -1;
                t++;
                start = Math.min(start, left);
                end = Math.max(end, right);
                idx--;
            }
            n = n - t + 1;
            idx++;
            int[][] ans = new int[n][];
            int i, j;
            for(i = 0, j = 0; i < n; i++){
                if(i == idx) ans[i] = new int[] {start, end};
                else{
                    while(intervals[j][0] == -1) j++;
                    ans[i] = intervals[j++];
                }
            }
            return ans;
        }
    }
}