435. Non-overlapping Intervals

Return the minimum number of intervals to remove so the remaining intervals do not overlap. Touching at an endpoint is fine.

Keep the interval that finishes earliest. It leaves the most room for the rest. Any interval starting before the last kept end must be removed.

1function eraseOverlapIntervals(intervals: number[][]): number {
2  intervals.sort((a, b) => a[1] - b[1]);
3  let end = -Infinity, removed = 0;
4  for (const [s, e] of intervals) {
5    if (s >= end) end = e;
6    else removed++;
7  }
8  return removed;
9}

end = -∞removed = 0

sorted by end

[1,2]

[2,3]

[1,3]

[3,4]

Sort by end time.

1 / 0

Space: play/pause · ←/→: step