Insert Interval

Problem

https://leetcode.com/problems/insert-interval/

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the i^th interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

• 0 <= intervals.length <= 10⁴

• intervals[i].length == 2

• 0 <= start_i<= end_i<= 10⁵

• intervals is sorted by start_i in ascending order.

• newInterval.length == 2

• 0 <= start <= end <= 10⁵

Pattern

Array, Intervals

Approaches

Greedy

Code

def insert(
    intervals: list[list[int]], newInterval: list[int]
) -> list[list[int]]:
    """Insert *newInterval* into sorted *intervals*, merging overlaps."""
    if not intervals:
        return [newInterval]

    c, d = newInterval
    result: list[list[int]] = []
    for i, (a, b) in enumerate(intervals):
        if d < a:
            result.append([c, d])
            return result + intervals[i:]
        elif c > b:
            result.append([a, b])
        else:
            c = min(a, c)
            d = max(b, d)

    result.append([c, d])
    return result

Test

>>> from insert_interval__greedy import insert
>>> insert([[1, 3], [6, 9]], [2, 5])
[[1, 5], [6, 9]]
>>> insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])
[[1, 2], [3, 10], [12, 16]]
>>> insert([], [5, 7])
[[5, 7]]

insert_interval__greedy.insert(intervals: list[list[int]], newInterval: list[int]) → list[list[int]]

Insert newInterval into sorted intervals, merging overlaps.

Insert Then Merge

Code

def insert(
    intervals: list[list[int]], newInterval: list[int]
) -> list[list[int]]:
    """Insert *newInterval* then merge overlapping intervals."""
    if not intervals:
        return [newInterval]

    new_start, new_end = newInterval
    for i, (start, end) in enumerate(intervals):
        if start >= new_start:
            intervals.insert(i, newInterval)
            break
    else:
        intervals.append(newInterval)

    result = [intervals[0]]
    for i in range(1, len(intervals)):
        a, b = result[-1]
        c, d = intervals[i]
        if c <= b:
            result[-1] = [a, max(b, d)]
        else:
            result.append([c, d])

    return result

Test

>>> from insert_interval__insert_then_merge import insert
>>> insert([[1, 3], [6, 9]], [2, 5])
[[1, 5], [6, 9]]
>>> insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])
[[1, 2], [3, 10], [12, 16]]
>>> insert([], [5, 7])
[[5, 7]]

insert_interval__insert_then_merge.insert(intervals: list[list[int]], newInterval: list[int]) → list[list[int]]

Insert newInterval then merge overlapping intervals.