LeetCode 57. Insert interval

57. Insert interval

 

 

【 Ordered set + Interval merging 】 Put all the intervals into an ordered set , Sort by left endpoint , For New Area new[start, end], Find the first left endpoint <=end The range of （floor Method ）, Judge whether the right endpoint of this interval >=start, If so, merge （ The merging method is actually taking new And the smaller value of the left endpoint of this interval , The larger value of the right endpoint ）, And delete the original interval , Then continue to find the next qualified interval that can be merged , Until all the intervals within the coverage are merged . sign out while After the cycle, the latest [start, end] Just join the collection .

class Solution {

    //  Ordered set  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;
    }
}

【 Two points + Interval merging 】 Suddenly found that the interval has been orderly , So don't open it again TreeSet 了 （ Actually use TreeSet） Mainly to use his floor Method , You can directly use two points to check , Then find the subscript and continue to look for it .

class Solution {

    //  Two points  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;
        }
    }
}