DSA problem
Insert Interval
You are given an array of non-overlapping intervals intervals sorted by their start times, and a new interval newInterval = [start, end] to insert. Insert newInterval into intervals such that the result is still sorted by start time and contains no overlapping intervals (merging if necessary). Return the resulting list.
Because intervals is already sorted and non-overlapping, you do not need to re-sort. A clean three-phase approach handles the work in a single linear pass. Phase one copies every interval that ends strictly before newInterval starts: these are untouched by the insertion and belong at the front of the result.
Phase two merges all intervals that overlap with newInterval. An interval [a, b] overlaps with newInterval when a <= newInterval[1] and b >= newInterval[0]. In the sorted scan, after phase one we walk through every interval whose start is at most newInterval[1], expanding newInterval to absorb each one: newInterval[0] = min(newInterval[0], a) and newInterval[1] = max(newInterval[1], b). After the loop append the (possibly grown) newInterval to the result.
Phase three copies all remaining intervals (those that start strictly after newInterval[1]) unchanged. Each input interval is visited at most once, so the total time is O(n) with O(n) output space.
Examples
intervals = [[1,3],[6,9]], newInterval = [2,5][[1,5],[6,9]]intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8][[1,2],[3,10],[12,16]]intervals = [], newInterval = [5,7][[5,7]]Constraints
- 0 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= start_i <= end_i <= 10^5
- intervals is sorted by start_i in ascending order.
- newInterval.length == 2
- 0 <= newInterval[0] <= newInterval[1] <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.