Single problem for Singles’ Day :P.

57. Insert Interval

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].

My accepted code can be found here

The original problem is, given a set of intervals and an interval, returning the new set of intervals, so the best time complexity is O(n) since we have to copy those unmodified interval into the new set, and the naive O(n) solution is trivial.

What we can optimize is the merging process of interval. Since the interval set given is sorted and unoverlapped, so we do it by binary search. Finally, the basic idea is that, we find the range of intervals that need to be merged, construct a new interval, then copy the intervals both before the range and after the range into the result.

There may be a lot of way to solve this. I did it by, find the last interval that start before the new one, and the first interval that end after the interval. If either of these two interval is overlapped with the new interval, include it to the range of modified interval and set the boundary of the new interval accordingly. And here’s the algorithm.

InsertInterval(intervals: Interval[], itv: Interval): Interval[] {
    define newItv: Interval
    let s = last interval that s.start < itv.start in intervals
    if s doesn't exist or s.end < itv.start {
        newItv.start = itv.start
    } else {
        newItv.start = s.start
        s = the interval directly before s in intervals
    }
    let e = first interval that e.end > itv.end in intervals
    if e doesn't exist or e.start > itv.end {
        newItv.end = itv.end
    } else {
        newItv.end = e.end
    }
    let result = empty Interval[]
    copy from beginning of intervals until s to result
    append newItv to result
    copy from e to the end of intervals
    return result
}

Time complexity is O(n)

Last

Nope