Greedy Algorithms8 sections · 316 units
Open in Course

Non-overlapping - The Idea

Maximize to minimize

The insight: minimum removals equals total intervals minus maximum you can keep. If you have nn intervals and can keep at most kk non-overlapping, you must remove nkn - k.

This transforms the problem into activity selection. Find the maximum non-overlapping set, then subtract from total. You already know how to maximize: sort by end time and greedily select. Without this transformation, you would try removing intervals in many different orders.