Overview

Given an array of intervals where intervals[i] = [start, end], return the minimum number of intervals you need to remove to make the rest non-overlapping.

Intervals that only touch at a point (e.g. [1,2] and [2,3]) are not overlapping.

Constraints

• 1 <= intervals.length <= 100,000
• intervals[i].length === 2
• -50,000 <= start < end <= 50,000

Examples

eraseOverlap([[1,2], [2,3], [3,4], [1,3]]);
// => 1  (remove [1,3] to keep [1,2], [2,3], [3,4])

eraseOverlap([[1,2], [1,2], [1,2]]);
// => 2  (keep one, remove two)

eraseOverlap([[1,2], [2,3]]);
// => 0  (already non-overlapping)

Solution

function eraseOverlap(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let count = 0;
  let prevEnd = -Infinity;

  for (const [start, end] of intervals) {
    if (start >= prevEnd) {
      prevEnd = end;
    } else {
      count++;
    }
  }

  return count;
}

Resources

• Non-overlapping Intervals — LeetCode
• Interval Scheduling — Wikipedia