Non-overlapping Intervals

The problem

Given intervals [start, end], return the minimum number of intervals to remove to make the rest non-overlapping. Touching endpoints typically do not count as overlap.

Input:  [[1,2],[2,3],[3,4],[1,3]]
Output: 1   // remove [1,3]

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

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

Equivalent view: maximum number of non-overlapping intervals you can keep; answer = n - kept.

Brute force

Try all subsets — exponential. Not interview-viable.

Optimal: greedy sort by end

Always keep the interval that ends earliest among candidates — leaves most room for the rest (classic activity selection).

function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) return 0;

  intervals.sort((a, b) => a[1] - b[1]);

  let kept = 1;
  let prevEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    if (start >= prevEnd) {
      kept++;
      prevEnd = end;
    }
    // else: overlap → skip (remove) this one
  }

  return intervals.length - kept;
}

Count removals directly:

function eraseOverlapIntervalsCount(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);
  let removals = 0;
  let prevEnd = -Infinity;

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

Time	O(n log n)
Space	O(1) extra (sort may use O(n))

Why not sort by start?

You can, but when two intervals overlap you must drop the one with the later end. Sorting by end encodes that choice automatically.

// sort by start variant
function eraseByStart(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
  let removals = 0;
  let prevEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    if (start < prevEnd) {
      removals++;
      prevEnd = Math.min(prevEnd, end); // keep earlier end
    } else {
      prevEnd = end;
    }
  }
  return removals;
}

Edge cases

• Empty → 0
• All nested → keep shortest-ending chain
• Already non-overlapping → 0
• Identical intervals → remove n−1

Common bugs

• Sorting by start and always removing the current without min-end logic
• Treating start == prevEnd as overlap
• Returning kept instead of n - kept

Interview delivery

1. Min removals = n − max non-overlapping.
2. Activity selection: sort by end.
3. Greedy keep.
4. O(n log n).
5. Contrast with merge / meeting rooms.

Related

• Meeting Rooms
• Meeting Rooms II
• Merge Intervals
• Insert Interval

Activity selection connection

Max non-overlapping intervals is the classic greedy: always take the meeting that finishes first. Min removals is the complement count. Proving greediness: any optimal solution can swap to include the earliest-ending interval without hurting capacity.

Compare sort keys

Sort by	Use
end ascending	max keep / min remove (this problem)
start ascending	merge intervals, meeting rooms I
start + min-heap ends	meeting rooms II

Naming the sort key is half the interview answer.

Further reading

• LeetCode 435 — Non-overlapping Intervals
• Activity selection problem