57. Insert Interval

Insert newInterval into a sorted list of non-overlapping intervals, merging where necessary so the list stays sorted and non-overlapping.

The list is sorted and disjoint. Copy intervals that end before the new one, merge every interval that overlaps it, then copy the rest.

1function insert(intervals: number[][], newInterval: number[]): number[][] {
2  const res: number[][] = [];
3  let [s, e] = newInterval, i = 0;
4  while (i < intervals.length && intervals[i][1] < s) res.push(intervals[i++]);
5  while (i < intervals.length && intervals[i][0] <= e) {
6    s = Math.min(s, intervals[i][0]);
7    e = Math.max(e, intervals[i][1]);
8    i++;
9  }
10  res.push([s, e]);
11  while (i < intervals.length) res.push(intervals[i++]);
12  return res;
13}

s = 4e = 8i = 0

intervals (new one last)

[1,2]

[3,5]

[6,7]

[8,10]

[12,16]

[4,8]

116

result

empty

Merging window starts as [4,8].

1 / 0

Space: play/pause · ←/→: step