Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Non-overlapping Intervals

Minimum removals

Given intervals, find the minimum number to remove so the rest do not overlap.

Here's activity selection in disguise! Maximum non-overlapping = minimize removals. If you can keep kk intervals, you remove nkn - k. Same algorithm: sort by end time, count max non-overlapping, subtract from nn. The problem asks for removals, but the underlying structure is identical to activity selection. You are maximizing what you keep, which minimizes what you remove.