Insert Interval
Problem
Given non-overlapping intervals sorted by start and a new interval, insert the new interval and merge wherever needed, so that the result is still sorted and non-overlapping.
Example 1
Input: intervals = [[1,3], [6,9]], new = [2,5] Output: [[1,5], [6,9]]
Example 2
Input: [[1,2],[3,5],[6,7],[8,10],[12,16]], new = [4,8] Output: [[1,2], [3,10], [12,16]]
Test cases
Case 1
Input: [[1,3],[6,9]], [2,5] Expected: [[1,5],[6,9]]
Case 2
Input: [[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8] Expected: [[1,2],[3,10],[12,16]]
Case 3
Input: [], [5,7] Expected: [[5,7]]
View solutionHide solution1 approach
1. Three phases in one pass
Time O(n)Space O(n)
Input is sorted and non-overlapping. Copy intervals ending before the new one, merge every interval that overlaps it, then copy the rest.
function insert(intervals, [s, e]) { const res = []; let i = 0; while (i < intervals.length && intervals[i][1] < s) res.push(intervals[i++]); while (i < intervals.length && intervals[i][0] <= e) { s = Math.min(s, intervals[i][0]); e = Math.max(e, intervals[i][1]); i++; } res.push([s, e]); while (i < intervals.length) res.push(intervals[i++]); return res;}