57.md

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 thoughts:

1. edge cases: not intervals, return newInterval; nI in front of intervals[0], concatnate; nI after intervals[-1], concatnate;
 iterate, if cur.end<nI.start, move on to next; if cur.start>nI.end, insert; if cur.start<=nI.end, start merging.
time: O(n); space: O(1)

my solution:

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

class Solution:
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        res = []
        first = True
        i = 0
        l = len(intervals)
        if not intervals or newInterval.end < intervals[0].start:
            return [newInterval] + intervals
        for i in range(l):
            if intervals[i].end < newInterval.start:
                res.append(intervals[i])
            elif intervals[i].start > newInterval.end:
                res.append(newInterval)
                j = 0
                while i+j < l:
                    res.append(intervals[i+j])
                    j += 1
                break
            else:
                intervals[i].start = min( intervals[i].start, newInterval.start )
                intervals[i].end = max( intervals[i].end, newInterval.end)
                res.append(intervals[i])
                j = 1
                while i+j < l:
                    if intervals[i+j].start<=res[-1].end:
                        res[-1].end = max( res[-1].end, intervals[i+j].end )
                    else:
                        res.append(intervals[i+j])
                    j += 1
                break
        if newInterval.start > res[-1].end:
            res.append(newInterval)
            
        return res

my comments:

from other ppl's solution:

1. kind of divide and conquer, 89ms:
# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        left_intervals, right_intervals = [], []
        start = newInterval.start
        end = newInterval.end
        for interval in intervals:
            if interval.end < start:
                left_intervals.append(interval)
            elif interval.start > end:
                right_intervals.append(interval)
            else:
                start = min(interval.start, start)
                end = max(interval.end, end)
        return left_intervals + [Interval(start, end)] + right_intervals