Insert Interval

medium

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i], sorted in ascending order by start_i. You are also given an interval newInterval.

Insert newInterval into intervals so that the list is still sorted and still contains no overlapping intervals — merging where necessary.

Return the resulting list of intervals.

Test Cases

Copy an input into the main harness and Run to verify

Input

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

Expected Output

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

Explanation: [2,5] overlaps [1,3], so they merge into [1,5].

Input

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

Expected Output

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

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

Constraints

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^5
intervals is sorted by start_i in ascending order.

Hints

Hint 1 — click to reveal

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

Hint 2 — click to reveal

Walk in three phases: intervals entirely before the new one, intervals that overlap it, then everything after.

Java Compiler