57_Insert Interval

[Hard][Array, Sort]

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

Output: [[1,5],[6,9]]

Example 2:

Input: intervals = 
[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Solution 1: Linear Search

Idea:

• First search for the position where we should insert or merge the new interval. The intervals on the left will be neglected.

• Then search for the position where we end insertion or merge. The intervals on the right will be neglected.

• Finally insert or merge the new interval.

Time Complexity: $O(n)$

Space Complexity: $O(1)$

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

def insert(intervals, newInterval):
    """
    :type intervals: List[Interval]
    :type newInterval: Interval
    :rtype: List[Interval]
    """
    # sort the intervals by starting point
    # intervals.sort(key=lambda x: x.start)

    # search the position to start insert/merge
    i = 0
    while i < len(intervals) and newInterval.start > intervals[i].end:
        i += 1
    # if the starting point of new interval is larger than every interval
    # insert new interval to the end
    if i == len(intervals):
        return intervals + [newInterval]

    # search the position to finish insert/merge
    j = i
    while j < len(intervals) and newInterval.end >= intervals[j].start:
        j += 1

    if j == i:
        # insert the new interval
        intervals[i:j] = [newInterval]
    else:
        # merge the new interval with overlapping intervals
        left = min(intervals[i].start, newInterval.start)
        right = max(intervals[j-1].end, newInterval.end)
        # insert into the intervals
        intervals[i:j] = [Interval(left, right)]
    return intervals

Solution 2: Binary Search

Idea:

• Extract all the starting values from the intervals, find the right place to insert the starting point in the new interval by binary search

• Extract all the ending values from the intervals, find the right place to insert the ending point in the new interval bu binary search

• Insert or merge the new interval into the overlapping place.

Time Complexity: $O(\log{n})$

Space Complexity: $O(1)$

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

def insert(intervals, newInterval):
    """
    :type intervals: List[Interval]
    :type newInterval: Interval
    :rtype: List[Interval]
    """        
    left, right = newInterval.start, newInterval.end
    start = [interval.start for interval in intervals]
    end = [interval.end for interval in intervals]
    i = bisect.bisect_left(start, left)
    j = bisect.bisect(end, right)
    if i > 0 and left <= intervals[i-1].end:
        left = intervals[i-1].start
        i = i - 1
    if j < len(intervals) and right >= intervals[j].start:
        right = intervals[j].end
        j = j + 1
    intervals[i:j] = [Interval(left, right)]
    return intervals