Insert Interval

Medium

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]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}