Asked at

Insert Interval

Medium
VerifiedArrayIntervals~25 min

Given a sorted, non-overlapping list of intervals and a newInterval, insert the new interval and merge any overlaps. Return the result sorted ascending by start. Treat touching endpoints as overlapping.

The input arrives as a single object { intervals, newInterval }.

Examples

in{ intervals: [[1, 3], [6, 9]], newInterval: [2, 5] }
out[[1, 5], [6, 9]]

[2,5] overlaps [1,3], merging into [1,5].

in{ intervals: [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval: [4, 8] }
out[[1, 2], [3, 10], [12, 16]]

[4,8] spans [3,5], [6,7], and [8,10], merging them into [3,10].

Constraints

  • 0 ≤ intervals.length ≤ 10⁴
  • intervals is sorted ascending by start and has no overlaps.
  • intervals[i] == [start, end] with start ≤ end
  • 0 ≤ start ≤ end ≤ 10⁵

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.