Intervals & Greedy · 085Medium
Insert Interval
Given a list of non-overlapping intervals sorted by start, insert a new interval and merge where necessary. Return the resulting sorted, non-overlapping list.
Constraints
- 0 <= intervals.length <= 10^4
- intervals is sorted by start and non-overlapping.
- 0 <= start <= end <= 10^5
Examples
insert([[1,3],[6,9]], [2,5]) -> [[1,5],[6,9]] insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]) -> [[1,2],[3,10],[12,16]] insert([], [5,7]) -> [[5,7]] insert([[3,5]], [1,2]) -> [[1,2],[3,5]] // goes before all, no overlap insert([[1,5]], [6,8]) -> [[1,5],[6,8]] // goes after all, no overlap insert([[1,2],[5,6]], [2,5]) -> [[1,6]] // touches both ends, all merge
Edge cases
- An empty input list.
- The new interval may go before all, after all, or swallow several.
- Touching endpoints ([1,2] and [2,3]) merge.
Show the target complexity (spoiler)
- Naive
- O(n log n) time — append the interval, re-sort, and run a full merge pass.
- Target
- O(n) time — the input is already sorted, so emit everything ending before the new start, merge the overlapping run, then emit the rest.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/11-intervals-greedy/085-insert-interval.js ./practice c 085