Hints — p48 Non-overlapping Intervals

Hint 1. “Min remove to make disjoint” = n - max disjoint subset size. Focus on maximizing the KEEP count.

Hint 2. Greedy. But what’s the sort key? Try [[1, 100], [2, 3], [4, 5]] mentally with sort-by-start: you’d keep [1, 100] and discard 2 others. That’s a 2-remove. Bad.

Hint 3. Sort by END time. Then keep any interval whose start >= prev_kept_end; else discard. Re-check the same input — you’ll keep [2,3] and [4,5], discard only [1,100]. 1 remove.

Hint 4. Why sort-by-end is optimal: exchange argument. The earliest-ending kept interval leaves the MOST room for future intervals. Any optimal solution can be rewritten swap-by-swap into the greedy without shrinking.

Hint 5. ASK: half-open or closed? LC 435 is HALF-OPEN — [1, 2] and [2, 3] do NOT overlap. So the keep condition is start >= prev_end (with >=, not >).

If still stuck: see solution.py.