Medium

Insert Interval

074

Insert newInterval into sorted non-overlapping intervals and return the merged result.

EXAMPLES

Example 1

Input
{
  "intervals": [
    [
      1,
      3
    ],
    [
      6,
      9
    ]
  ],
  "newInterval": [
    2,
    5
  ]
}

Output
[
  [
    1,
    5
  ],
  [
    6,
    9
  ]
]

FUNCTION SHAPE

intervals: intMatrixnewInterval: intArray→intMatrix

SOLUTION NOTE

The key is to realize that there are 3 ranges to the answer. The first list of intervals that don't overlap to the left of the inserted one. The list of intervals in the middle that overlap with the inserted one, that we have to merge together. And the list of intervals to the right that don't overlap. Now the question is, what are these indices i,j that define this middle list of intervals that overlap?

There's two ways. First is a linear scan to find starting i and ending j indices that define the range we should merge. Second is using binary search.

Both are O(n) time and space. You might wonder why we would use binary search if the complexity is the same? Look at the Count Integers in Intervals question :)

Reveal reference solution +

pythonREFERENCE

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort()
    res = []
    for s, e in intervals:
        if res and s <= res[-1][1]:
            res[-1][1] = max(res[-1][1], e)
        else:
            res.append([s, e])
    return res

# Linear scan
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    i = 0
    n = len(intervals)
    c, d = newInterval

    while i < n and intervals[i][1] < c:
        i += 1
    j = n - 1
    while j >= 0 and d < intervals[j][0]:
        j -= 1

    merged = self.merge(intervals[i:j+1] + [newInterval])
    return intervals[:i] + merged + intervals[j+1:]

# Binary search
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    l, r = newInterval
    i = bisect_right(intervals, [l, inf]) - 1
    j = bisect_left(intervals, [r+1, -inf]) - 1
    i = max(0, i)
    merged = self.merge(intervals[i:j+1] + [newInterval])
    return intervals[:i] + merged + intervals[j+1:]

TimeO(n)

SpaceO(n)

Open on LeetCode ↗