You are given intervals, a list of ranges [start, end] sorted by start, in which no two ranges
overlap or touch. You are also given one more range, newInterval.
Insert newInterval and return the resulting list of ranges, sorted by start, with any ranges
that now overlap merged into one. Ranges that share even a single point overlap, so [1, 3] and
[3, 6] merge into [1, 6]. You may build a new list rather than change intervals.
Example 1
- Input
- intervals = [[1, 2], [4, 5], [7, 9], [12, 14]], newInterval = [5, 8]
- Output
- [[1, 2], [4, 9], [12, 14]]
[5, 8] touches [4, 5] at 5 and overlaps [7, 9], so the three become [4, 9].Example 2
- Input
- intervals = [[1, 3], [8, 10]], newInterval = [4, 6]
- Output
- [[1, 3], [4, 6], [8, 10]]
Constraints
intervalsholds 0 to 10⁴ ranges.- Every range,
newIntervalincluded, has 0 ≤start≤end≤ 10⁵. intervalsis sorted by start, and each range ends before the next one starts.
Show the pattern
Intervals
The ranges are already sorted and separate, so one pass splits them into three groups: those wholly before the new range, those that overlap it (merge them in), and those wholly after it.
See intervals in a visualiserShow the approach
Walk through intervals once, in three phases. First, every range that ends before newInterval
starts (end < newStart) comes before it untouched: copy it to the result. Next, every range that
starts no later than newInterval ends (start ≤ newEnd) overlaps it: widen the new range to the
smaller of the two starts and the larger of the two ends. Add the widened range. Finally, copy
the remaining ranges, which all start after it ends.
Time: O(n) · Space: O(n) for the result