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:

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

Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Thoughts:

1. Find the first and last interval index to merge(i,j) and merge them by creating a new interval with (min(firstInterval.start, newInterval.start), max(lastInterval.end, newInterva.end), and adding other intervals that is not merged.

   1. To find the first interval: incre i until intervals[i].end > newInterval.start

   2. To find the last interval: incre j until intervals[j].start > newInterval.end

   3. if i == j == 0; then only need to add _newinterval _in front

   4. if i == j == len, then only need to append _newinterval _in the end

2. One - Pass: Collect the intervals strictly left or right of the new interval, then merge the new one with the middle ones (if any) before inserting it between left and right ones. StefanPochmann's post

Code

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

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        res =[]
        i, j, n = 0, 0, len(intervals)
        while i < n:
            if intervals[i].end < newInterval.start:
                res.append(intervals[i])
                i +=1
            else: break

        while j < n:
            if intervals[j].start <= newInterval.end: j += 1
            else: break

        if i == j == 0:
            res.append(newInterval)
            res += intervals
            return res
        elif i == j == n:
            intervals.append(newInterval)
            return intervals

        merge = Interval(min(intervals[i].start, newInterval.start), max(intervals[j - 1].end, newInterval.end))
        res.append(merge)

        for k in range(j, n):
            res.append(intervals[k])
        return res

Code: Python One pass

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

class Solution(object):
    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        left, right = [], []
        for i in intervals:
            if i.end < s:
                left += i,
            elif i.start > e:
                right += i,
            else:
                s = min(s, i.start)
                e = max(e, i.end)
        return left + [Interval(s, e)] + right