Insert Intervals

Question

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

Example Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].

Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].

Thoughts

每一个现在的interval与新的interval相比，有三种情况

1. current [5,7] and new [1,2], since current.start > new.end, add new to results
2. current [1,2] and new [3,5], since current.end < new.start, add current to results
3. current [1,7] and new [2,3], since current.end > new.start, merge Interval.

Solution

"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""


class Solution:
    """
    Insert a new interval into a sorted non-overlapping interval list.
    @param intevals: Sorted non-overlapping interval list
    @param newInterval: The new interval.
    @return: A new sorted non-overlapping interval list with the new interval.
    """
    def insert(self, intervals, newInterval):
        results = []
        insertPos = 0
        length = len(intervals)
        for i in range(length):
            cur = intervals[i]
            if cur.end < newInterval.start:
                results.append(cur)
                insertPos += 1
            elif cur.start > newInterval.end:
                results.append(cur)
            else:
                newStart = min(cur.start, newInterval.start)
                newEnd = max(cur.end, newInterval.end)
                newInterval.start = newStart
                newInterval.end = newEnd
        results.insert(insertPos, newInterval)

        return results