Intervals

Insert Interval

medium

DESCRIPTION (inspired by Leetcode.com)

Given a list of intervals intervals and an interval newInterval, write a function to insert newInterval into a list of existing, non-overlapping, and sorted intervals based on their starting points. The function should ensure that after the new interval is added, the list remains sorted without any overlapping intervals, merging them if needed.

Input:

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

Output:

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

Explanation: The new interval [2,5] overlaps with [1,3], so they are merged into [1,5].

Code Editor

Run your code to see results here

Have suggestions or found something wrong?

Explanation

We first want to create a new list merged to store the merged intervals we will return at the end.

This solution operates in 3 phases:

Add all the intervals ending before newInterval starts to merged.
Merge all overlapping intervals with newInterval and add that merged interval to merged.
Add all the intervals starting after newInterval to merged.

Phase 1

In this phase, we add all the intervals that end before newInterval starts to merged. This involves iterating through the intervals list until the current interval no longer ends before newInterval starts (i.e. intervals[i][1] >= newInterval[0]).

Visualization


def insertIntervals(intervals, newInterval):
    merged = []
    i = 0
    n = len(intervals)
    while i < n and intervals[i][1] < newInterval[0]:
        merged.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(intervals[i][0], newInterval[0])
        newInterval[1] = max(intervals[i][1], newInterval[1])
        i += 1
    merged.append(newInterval)
    for j in range(i, n):
        merged.append(intervals[j])
    return merged

initialize variables

0 / 1

Phase 2

In this phase, we merge all the intervals that overlap with newInterval together into a single interval by updating newInterval to be the minimum start and maximum end of all the overlapping intervals. This involves iterating through the intervals list until the current interval starts after newInterval ends (i.e. intervals[i][0] > newInterval[1]). When that condition is met, we add newInterval to merged and move onto phase 3.

Visualization


def insertIntervals(intervals, newInterval):
    merged = []
    i = 0
    n = len(intervals)
    while i < n and intervals[i][1] < newInterval[0]:
        merged.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(intervals[i][0], newInterval[0])
        newInterval[1] = max(intervals[i][1], newInterval[1])
        i += 1
    merged.append(newInterval)
    for j in range(i, n):
        merged.append(intervals[j])
    return merged

add intervals before newInterval

0 / 4

Phase 3

Phase 3 involves adding all the intervals starting after newInterval to merged. This involves iterating through the intervals list until the end of the list, and adding each interval to merged.

After completing these 3 phases, we return merged as the final result.

Visualization


def insertIntervals(intervals, newInterval):
    merged = []
    i = 0
    n = len(intervals)
    while i < n and intervals[i][1] < newInterval[0]:
        merged.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(intervals[i][0], newInterval[0])
        newInterval[1] = max(intervals[i][1], newInterval[1])
        i += 1
    merged.append(newInterval)
    for j in range(i, n):
        merged.append(intervals[j])
    return merged

j = 4

0 / 2

What is the time complexity of this solution?

O(n³)

O(m * n * 4^L)

O(n)

O(4^L)

Solution

Try these examples:

Visualization


def insertIntervals(intervals, newInterval):
    merged = []
    i = 0
    n = len(intervals)
    while i < n and intervals[i][1] < newInterval[0]:
        merged.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(intervals[i][0], newInterval[0])
        newInterval[1] = max(intervals[i][1], newInterval[1])
        i += 1
    merged.append(newInterval)
    for j in range(i, n):
        merged.append(intervals[j])
    return merged

insert interval

0 / 9

Mark as read

Next: Non-Overlapping Intervals