Pattern Recognition Drill

#113 — Non-overlapping Intervals

Medium Intervals

The Problem

Given intervals, find the minimum number of intervals to remove to make the rest non-overlapping.

What approach would you use?

Think about it before scrolling down.

Key Signals

'Minimum removals' → greedy: keep as many as possible
'Non-overlapping' → classic activity selection: sort by end time, greedily keep non-overlapping

Greedy

Sort by end. Greedily keep intervals whose start >= last kept end. Removals = total - kept. O(n log n).

Alt: Dynamic Programming

LIS-style on intervals sorted by end. O(n²) — less efficient.

Common Trap

Sort by END time, not start time. Sorting by start can lead to suboptimal greedy choices.

← #112