Insert Interval

IntervalsArrays

20 min

Problem Statement

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 ith 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).

Example

Example 1:

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

Initial Intervals:

[1, 3]

[6, 9]

New Interval:

[2, 5]

Result:

[1, 5]

[6, 9]

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

Solution

The core idea is to find the correct place to insert the new interval and then merge it with any overlapping intervals.

Algorithm Steps

Create a new list to store the merged intervals.
Iterate through the original intervals and add all intervals that end before the new interval starts to the result list.
Merge the new interval with any overlapping intervals. The new interval becomes the union of itself and any interval it overlaps with.
Add the (possibly updated) new interval to the result list.
Add all remaining intervals from the original list to the result list.
Return the result list.

Original Intervals

[1, 2]

[3, 5]

[6, 7]

[8, 10]

[12, 16]

New Interval

[4, 8]

Result

Start: Initialize an empty result list.

Insert Interval Solution


class Solution:
    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
        res = []
        i = 0
        n = len(intervals)

        # Add all intervals that come before the new interval
        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1

        # Merge all overlapping intervals
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        res.append(newInterval)

        # Add all remaining intervals
        while i < n:
            res.append(intervals[i])
            i += 1
            
        return res