Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Minimum Intervals to Cover

Cover a range

Given intervals and a target range [0, T], find minimum intervals to cover the entire range.

Example: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 1010. Answer: 33. Use [0,2] or [1,5] to cover [0,2], then [1,9] to cover up to 99, then [8,10] to finish.

This is a covering problem, not a selection problem. Without greedy extension, you would try all combinations in exponential time.