Insert Interval

Description

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Show Company Tags Show Tags Show Similar Problems

Hint

Train of Thought

The idea is using binary search to find the position that the newInterval to be inserted.

Since the original intervals are sorted and disjoint, we can apply binary search to find the insertion index of newInterval.start (by interval.start), and to find the insertion index of newInterval.end(by interval.end), 【see LeeCode problem #35】. Then remove the overlapped elements of the list and merge the newInterval with boundary elements on two sides.

Complexity: O(log n) in time (in fact, depending on the implement of the access method list.get(i) and of list.subList(int, int).clear()); O(1) in space.

Code

 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    /**
     * Since the original list is sorted and all intervals are disjoint,
     * apply binary search to find the insertion index for the new
     * interval. [LC35]
     * 
     * 1. Find insIdx=the insertion index of new.start, i.e., the first
     * index i such that list.get(i).start>=new.start.
     * 
     * 2. Find nxtIdx=the insertion index of new.end, i.e., the first
     * index i such that list.get(i).end>=new.end.
     * 
     * 3. Remove all elements of the list with indices insIdx<=i<nxtIdx.
     * 
     * 4. Merge new with list.get(insIdx-1) or list.get(nxtIdx) or both.
     */

    int n = intervals.size();
    if (n == 0) {
        intervals.add(newInterval);
        return intervals;
    }

    int low = 0, high = n - 1, mid = 0;
    int temp, target = newInterval.start;
    while (low <= high) {
        mid = (low + high) / 2;
        temp = intervals.get(mid).start;
        if (temp == target)
            break;
        if (temp < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    // insIdx = the index where new interval to be inserted
    int insIdx = (low <= high) ? mid : low;
    Interval pre = (insIdx == 0) ? null : intervals.get(insIdx - 1);
    // 0<=insIdx<=n, pre=[insIdx-1], pre.start<new.start

    low = insIdx;
    high = n - 1;
    target = newInterval.end;
    while (low <= high) {
        mid = (low + high) / 2;
        temp = intervals.get(mid).end;
        if (temp == target)
            break;
        if (temp < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    // nxtIdx= the next index after the inserted new interval
    int nxtIdx = (low <= high) ? mid : low;
    Interval nxt = (nxtIdx == n) ? null : intervals.get(nxtIdx);
    // insIdx<=nxtIdx<=n, nxt=[nxtIdx], nxt.end>=new.end

    // [0]...[insIdx-1] <--> [insIdx]...[nxtIdx-1][nxtIdx]...[n]
    intervals.subList(insIdx, nxtIdx).clear();

    // check whether newInterval can be merged with pre or nxt
    boolean isMerged = false, isMerged2 = false;
    if (insIdx > 0 && pre.end >= newInterval.start) {
        pre.end = Math.max(pre.end, newInterval.end);
        isMerged = true;
    }

    if (nxtIdx < n && newInterval.end >= nxt.start) {
        nxt.start = Math.min(nxt.start, newInterval.start);
        isMerged2 = isMerged;
        isMerged = true;
    }

    if (!isMerged) {
        intervals.add(insIdx, newInterval);
        return intervals;
    }

    // merged with pre or nxt or both, deal with the both case
    if (isMerged2 && pre.end >= nxt.start) {
        nxt.start = pre.start; // pre.start < new.start, nxt.start;
        intervals.remove(insIdx - 1); // remove pre
    }

    return intervals;
}

Complexity