57.Insert Interval

Tags: [queue], [interval], [merge], [insert]

Com: {fb}

Link: https://leetcode.com/problems/insert-interval/\#/description

Given a set ofnon-overlappingintervals, 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].

Solution: Queue

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

from collections import deque

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        if not newInterval:
            return intervals
        if not intervals:
            return [newInterval]

        queue = deque()
        for i in xrange(len(intervals)):
            interval = intervals[i]

            if self.can_merge(interval, newInterval):
                self.merge_intervals(interval, newInterval)
                newInterval = None
                queue.append(interval)
                continue

            elif self.can_insert(intervals, i, newInterval):
                queue.append(newInterval)
                queue.append(interval)
                newInterval = None
                continue

            if not queue or not self.can_merge(queue[-1], interval):
                queue.append(interval)
            else:
                self.merge_intervals(queue[-1], interval)

        if newInterval:
            queue.append(newInterval)

        return list(queue)

    def can_merge(self, interval1, interval2):
        if not interval1 or not interval2:
            return False

        left = interval1 if interval1.start <= interval2.start else interval2
        right = interval1 if interval1.start > interval2.start else interval2

        return left.end >= right.start

    def merge_intervals(self, interval1, interval2):
        interval1.start = min(interval1.start, interval2.start)
        interval1.end = max(interval1.end, interval2.end)

    def can_insert(self, intervals, index, new_interval):
        if not new_interval:
            return False

        if index == 0:
            return new_interval.end < intervals[index].start

        return intervals[index - 1].end < new_interval.start and\
               new_interval.end < intervals[index].start

Revelation:

• First whether current interval can merge with newInterval, if they cannot be merged, then check can we insert the newInterval at the position i. Be careful the following cases: (1) intervals = [[1, 5]], newInterval = [0, 3]; (2) intervals = [[1, 3], [10, 15]], newInterval = [5, 6]. (3) Intervals = [[1, 3]], newInterval = [10, 15].

Note:

• Time complexity = O(n), n is the number of intervals.
• Space complexity = O(n), n is the number of intervals.
• Need check the following, at the beginning of the 'can_insert' function:

if not new_interval:
    return False