M.A.T.R.I.X

Appearance

4.27.3 — Non-overlapping Intervals ​

LeetCode 435 · Medium

The problem ​

Return the minimum number of intervals to remove so that the rest do not overlap.

[[1,2],[2,3],[3,4],[1,3]]   →  1     (remove [1,3])
[[1,2],[1,2],[1,2]]         →  2
[[1,2],[2,3]]               →  0     (touching is not overlapping here)

The pattern ​

Turn it round: removing the fewest is the same as keeping the most. So the question becomes what is the largest set of non-overlapping intervals I can keep? — and the answer is n minus that.

That is the activity selection problem, and it has a famous greedy:

Sort by end time, and always keep the interval that finishes earliest among those that still fit.

Why sort by end, not by start ​

This is the question, so here is the proof.

Finishing earliest leaves the most room for everything after it.

Formally, an exchange argument. Suppose some optimal solution does not include the interval that finishes earliest, call it x. Take the first interval in that solution, call it y. Since x finishes no later than y, swapping y for x cannot create a conflict with anything later — everything that fitted after y also fits after x. So there is an optimal solution containing x, and greedy is safe.

Sorting by start fails, and it is worth seeing why: a very long interval starting first would be taken and would block everything else. [[1,100],[2,3],[4,5]] — sorting by start keeps only [1,100]; sorting by end keeps two.

Sorting by length also fails. [[1,10],[9,12],[11,20]] — the shortest is [9,12], and taking it blocks both others, whereas keeping [1,10] and [11,20] gives two.

Having both counterexamples ready is a strong way to answer "why end time".

The solution ​

python
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])           # sort by END

        kept = 0
        last_end = float('-inf')

        for start, end in intervals:
            if start >= last_end:                     # no overlap with what we kept
                kept += 1
                last_end = end

        return len(intervals) - kept
ts
function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);

  let kept = 0, lastEnd = -Infinity;

  for (const [start, end] of intervals) {
    if (start >= lastEnd) {
      kept++;
      lastEnd = end;
    }
  }

  return intervals.length - kept;
}

start >= last_end uses >=, because touching intervals do not overlap in this problem — [1,2] and [2,3] can both be kept. Compare 4.27.2 Merge Intervals, where touching intervals do merge and the comparison is <=. Two adjacent problems, opposite conventions — this is exactly why you ask.

last_end starts at negative infinity, so the first interval is always kept.

Counting kept intervals and subtracting is cleaner than counting removals, because the greedy naturally decides what to keep.

Trace ​

[[1,2],[2,3],[3,4],[1,3]] sorted by end: [[1,2],[1,3],[2,3],[3,4]].

intervallast_endkeep?kept
[1,2]−∞yes1, end 2
[1,3]21 < 2 → no1
[2,3]22 ≥ 2 → yes2, end 3
[3,4]33 ≥ 3 → yes3, end 4

Kept 3, removed 4 − 3 = 1 ✓.

Complexity ​

O(n \log n) time from the sort, O(1) extra space.

The other interval greedy ​

The mirror problem — Minimum Number of Arrows to Burst Balloons (LeetCode 452) — is the same algorithm with the answer read differently.

You want the fewest points that touch every interval. Sort by end, shoot an arrow at the end of the first interval, skip everything it hits, and repeat. The number of arrows equals the number of intervals you would have "kept" here.

They are the same computation: the count of intervals kept is both the largest non-overlapping set and the fewest points needed to stab all of them. That duality is a nice thing to notice, and it is why the two problems have identical code.

Watch one detail there: touching balloons are burst by the same arrow, so the comparison flips to >.

Where this goes next ​

  • Merge Intervals — sort by start instead. 4.27.2.
  • Maximum Length of Pair Chain — identical to this problem, counting kept pairs directly.
  • Minimum Arrows to Burst Balloons — above.
  • Job Scheduling with profits — when intervals have values, greedy fails and it becomes DP with binary search, O(n \log n). That is the boundary: unweighted activity selection is greedy; weighted is DP. Naming it shows you know where the greedy stops working.

What the interviewer will push on ​

"Why sort by end?" The exchange argument, plus the [[1,100],[2,3],[4,5]] counterexample against sorting by start.

"Why not sort by length?" [[1,10],[9,12],[11,20]].

"Does touching count as overlapping?" Not here — hence >=. And it is the opposite convention to Merge Intervals, so ask on every interval problem.

"Why count kept rather than removed?" The greedy decides what to keep; removals are the leftover.

"What if intervals had weights?" Greedy breaks; it becomes DP with binary search.

One thing to volunteer: give the exchange argument before the code. This is the chapter where greedy proofs are short and expected, and one sentence of justification separates a correct solution from a lucky one.

Next: 4.27.4 Meeting Rooms — the simplest interval question there is, and the warm-up for the one after it.