Non-overlapping Intervals

Examples

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1

Removing [1,3] leaves [[1,2],[2,3],[3,4]], which only touch at shared endpoints, so nothing overlaps.

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2

All three intervals are identical and fully overlap, so two of the three must go, keeping just one.

Input: intervals = [[1,2],[2,3]]
Output: 0

These only touch at the point 2, which doesn't count as overlapping, so nothing needs to be removed.

Constraints

• 1 <= intervals.length <= 10^5

• intervals[i].length == 2

• -5 * 10^4 <= start < end <= 5 * 10^4

Approach

One way to attack this is with dynamic programming: sort by start time, and for each interval work out the longest chain of non-overlapping intervals that could end there, by checking every earlier interval that doesn't conflict with it. The answer is then the total count minus the longest such chain. It's correct, but it's checking a lot of pairs that a smarter order would let you skip.

The faster route is a classic greedy trick: sort by end time. Then walk through the intervals keeping track of the end time of the last interval you decided to keep. Whenever the next interval starts before that end time, it overlaps, so it's the one you remove (never the one you already kept — it had the earliest possible end, so it's always the safer one to hang onto). Every time you don't need to remove one, update your "last kept end" to the new interval's end.

Solutions

Brute Force — DP on Longest Non-overlapping Chain

Sort intervals by start time. For each interval i, look at every earlier interval j that ends at or before interval i starts — those two could both be kept together. dp[i] stores the length of the longest chain of mutually non-overlapping intervals that ends with interval i. The largest value in dp is the most intervals you can keep overall, so the number to remove is the total count minus that maximum.

function eraseOverlapIntervals(intervals) {
  const n = intervals.length;
  if (n === 0) return 0;

  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const dp = new Array(n).fill(1);
  let maxKept = 1;

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (sorted[j][1] <= sorted[i][0]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxKept = Math.max(maxKept, dp[i]);
  }

  return n - maxKept;
}

Time: O(n^2) — for each interval, scan every earlier interval · Space: O(n) for the dp array

Optimal — Greedy, Sort by End Time

Sort the intervals by their end time. Walk through them left to right, tracking the end time of the last interval you've decided to keep (start with the first interval always kept, since it has the earliest possible end).

For each next interval, if its start is at or after that tracked end time, it doesn't overlap what you've kept — keep it too, and update the tracked end. If its start is before that end time, it overlaps, so it must be removed; count it, but leave the tracked end alone, since the interval you already kept still ends earlier and stays the better anchor.

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;

  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let lastEnd = sorted[0][1];
  let keptCount = 1;

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] >= lastEnd) {
      keptCount++;
      lastEnd = sorted[i][1];
    }
  }

  return sorted.length - keptCount;
}

Time: O(n log n) — dominated by the sort · Space: O(n) for the sorted copy