Insert a new interval into a set of non-overlapping sorted intervals and merge any overlaps.
Problem
You are given a list of non-overlapping intervals sorted by their start values, and a single new interval. Insert the new interval into the list so that the final set of intervals remains sorted by start time and contains no overlaps.
If the new interval overlaps one or more existing intervals, merge them into one interval that covers the entire combined range.
Return the resulting list of intervals.
Notes
- Intervals are inclusive of their endpoints.
- The input intervals are already sorted by start value and do not overlap with each other.
- The new interval may overlap none, one, or many existing intervals.
Input Format
- A list of intervals
intervals, where each interval is[start, end]. - A single interval
newInterval = [start, end].
Each interval uses integer endpoints and satisfies start <= end.
Output Format
- Return a list of intervals in sorted order by start value.
- The returned intervals must be pairwise non-overlapping.
Constraints
0 <= intervals.length <= $10^{4}$intervals[i].length == 20 <= start <= end- The intervals are sorted by increasing start value.
- The intervals do not overlap each other.
newInterval.length == 2
Example 1
Input
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output
[[1,5],[6,9]]
Explanation
The new interval overlaps with [1,3], so they merge into [1,5]. The interval [6,9] stays unchanged.
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 new interval overlaps with [3,5], [6,7], and [8,10], so all of them merge into [3,10].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.