Insert Interval

Medium· Sweep

Problem

You have a list of non-overlapping intervals sorted by start, and one new interval. Insert the new interval so the list stays sorted and non-overlapping, merging wherever necessary, and return the result.

Examples

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

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

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

Output: [[1,2],[3,10],[12,16]]

[4,8] overlaps [3,5], [6,7] and [8,10], which all fuse into [3,10].

Constraints

• 0 <= intervals.length <= 10^4
• intervals is sorted by start and non-overlapping
• 0 <= start <= end <= 10^5

Hints & approach

Hint 1

The input is already sorted, so you do not need to sort again.

Hint 2

Split the list into three parts: entirely before the new interval, overlapping it, and entirely after.

Hint 3

Everything in the middle part collapses into one interval with the min start and max end.

Approachtry the hints first

Scan once. Copy every interval that ends before the new one starts. Then, while intervals start at or before the new interval's end, absorb them by taking the minimum start and maximum end. Append the merged interval, then copy the remaining intervals unchanged. This is a single linear pass with no sorting.

Time O(n) · Space O(n)

← PreviousMerge Intervals Next →Non-overlapping Intervals