Insert Interval

Given a set of non-overlapping intervals sorted by start time and a new interval, insert the new interval and merge where needed. The problem becomes simple once the intervals are processed in sorted order.

Input Format

intervals = sorted array of intervals, newInterval = interval to insert

Output Format

intervals after insertion and merging

Constraints

  • 0 <= intervals.length <= 10^4; intervals are non-overlapping and sorted by start time

Examples

Example 1:

Input:

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

Output:

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

Explanation:

The new interval overlaps with [1,3] and merges into [1,5].

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:

The inserted interval bridges multiple adjacent intervals.

Loading...
Insert Interval - Sorting Based Array Problems