Insert Interval

Question

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

Tag

• Array
• Sort

Thought

Reference: https://discuss.leetcode.com/topic/16988/7-lines-3-easy-solutions

Split the sorted interval list according to the new interval and update the new interval according to the splitting result.

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]
        """
        s, e = newInterval.start, newInterval.end
        left = [item for item in intervals if item.end < s]
        right = [item for item in intervals if item.start > e]

        if left + right != intervals:
            s = min(s, intervals[len(left)].start)
            e = max(e, intervals[-1-len(right)].end)

        return left + [Interval(s, e)] + right