Insert Interval
MediumIntervals
You get a list of intervals, each [start, end], sorted by start and with no two overlapping, and one more interval, newInterval. Add newInterval to the list, merging it with every interval it overlaps, and return the new list.
The answer must also be sorted by start with no overlaps. Two intervals that only touch, like [1, 3] and [3, 6], count as overlapping and merge into [1, 6].
Examples
Input: intervals = [[1, 2], [4, 6], [9, 12]], newInterval = [5, 8] Output: [[1, 2], [4, 8], [9, 12]]
[5, 8] overlaps [4, 6] only, and the two become [4, 8].
Input: intervals = [[2, 3], [5, 7], [8, 10], [13, 15]], newInterval = [6, 14] Output: [[2, 3], [5, 15]]
[6, 14] reaches into three intervals, from [5, 7] to [13, 15], and swallows all of them.
Constraints
0 ≤ intervals.length ≤ 10⁴0 ≤ start ≤ end ≤ 10⁵for every interval,newIntervaltoo.intervalsis sorted by start and has no overlaps.
Stuck?
Hint 1
The list falls into three runs: intervals that end before newInterval starts, intervals that overlap it, and intervals that start after it ends.
Hint 2
Copy the first run as it is. Grow newInterval over the second run (smallest start, largest end), push it, then copy the third run.
The idea
Because the list is sorted and has no overlaps, it splits into three runs: intervals that end before newInterval starts, intervals that overlap it, and intervals that start after it ends. One pass copies the first run, folds the middle run into newInterval, and copies the last run.
Time O(n)Extra space O(n) for the answer
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
start and end hold newInterval as it grows. One index i walks the list once and carries on from each loop into the next.
function insert(intervals, newInterval) { const answer = []; let [start, end] = newInterval; let i = 0; while (i < intervals.length && intervals[i][1] < start) answer.push(intervals[i++]); while (i < intervals.length && intervals[i][0] <= end) { start = Math.min(start, intervals[i][0]); end = Math.max(end, intervals[i][1]); i++; } answer.push([start, end]); while (i < intervals.length) answer.push(intervals[i++]); return answer;}The trap
The three runs are right, but both boundaries treat touching as not overlapping. An interval that ends exactly where newInterval starts is copied as it is, and one that starts exactly where it ends is left for the last run. The problem counts touching as overlap, so a newInterval that only meets a neighbour at an end point comes back as two intervals instead of one.
function insert(intervals, newInterval) { const answer = []; let [start, end] = newInterval; let i = 0; while (i < intervals.length && intervals[i][1] <= start) answer.push(intervals[i++]); // touching is left unmerged while (i < intervals.length && intervals[i][0] < end) { start = Math.min(start, intervals[i][0]); end = Math.max(end, intervals[i][1]); i++; } answer.push([start, end]); while (i < intervals.length) answer.push(intervals[i++]); return answer;}