57. Insert Interval

二刷 06/2022

Version #1 Scan the Array

因为bottle neck是scan the array所以不需要用到binary search

思路就是先把前面不overlap的加上，然后计算overlap的，最后再把后面不overlap的加上

看起来不难但是自己竟然写不出来

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 99.71% of Java online submissions for Insert Interval.

Memory Usage: 44.5 MB, less than 90.60% of Java online submissions for Insert Interval.

class Solution {

    public int[][] insert(int[][] intervals, int[] newInterval) {

        List<int[]> result = new ArrayList<>();

        int index = 0;

        int start = newInterval[0], end = newInterval[1];

        while (index < intervals.length && intervals[index][1] < start) {

            result.add(intervals[index++]);

        }

        while (index < intervals.length && intervals[index][0] <= end) {

            start = Math.min(start, intervals[index][0]);

            end = Math.max(end, intervals[index][1]);

            index++;

        }

        result.add(new int[]{start, end});

        while (index < intervals.length) {

            result.add(intervals[index++]);

        }

        return result.toArray(new int[0][]);

    }

}

一刷
一万个edge case

                         [first]
[newInterval]

[first]
              [newInterval]

                        [second]
[newInterval]
[second]
              [newInterval]


left = 1
right = 0

[[3,5],[12,15]]
[6,6]

100.00 %
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            result.add(newInterval);
            return result;
        }
        // 1 find the first interval whose end >= newInterval.start
        // 2 find the last interval whose start <= newInterval.end
        int start = 0;
        int end = intervals.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (intervals.get(mid).end < newInterval.start) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
       
        Interval first = intervals.get(start);
        int left = start;
        if (newInterval.end < first.start) {
            left--;
        } else if (first.end < newInterval.start) {
            left++;
        }
       
        start = 0;
        end = intervals.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (intervals.get(mid).start > newInterval.end) {
                end = mid  - 1;
            } else {
                start = mid;
            }
        }
        int right = end;
        Interval second = intervals.get(end);
        if (second.start > newInterval.end) {
            second = intervals.get(start);
            right = start;
        }
        if (newInterval.end < second.start) {
            right--;
        } else if (second.end < newInterval.start) {
            right++;
        }
       
        int i = 0;
        while (i < left) {
            result.add(intervals.get(i));
            i++;
        }
        if (left >= 0 && left < intervals.size()) {
            if (intervals.get(left).end >= newInterval.start) {
               
                newInterval.start = Math.min(intervals.get(left).start, newInterval.start);
            } else {
                result.add(intervals.get(left));
            }
        }
       
        result.add(newInterval);
        if (right >= 0 && right < intervals.size()) {
            if (intervals.get(right).start <= newInterval.end) {
                newInterval.end = Math.max(intervals.get(right).end, newInterval.end);
            } else {
                result.add(intervals.get(right));
            }
        }
       
        i = right + 1;
        while (i < intervals.size()) {
            result.add(intervals.get(i));
            i++;
        }
        return result;
    }
}