Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 20m 21s17 days 22 hours 20 minutes 21 seconds.

Algorithms - Greedy · 4:07

Interval Scheduling

To accept the most non-overlapping requests on one resource, sort by end time and take every request that starts no earlier than the last one taken ends: on [1,3] [2,5] [4,6] [6,8] [5,9] [8,10] that keeps four. We prove it with 'greedy stays ahead', settle whether touching endpoints conflict, and break the two tempting wrong keys (earliest start, shortest first) with counterexamples and a stress test on 5000 random inputs. Then the covering twin: fill the trading day [0, 10] with the fewest shifts by always jumping to the farthest reach.

You will learn

Select the maximum number of non-overlapping intervals by sorting on end time, in O(n log n)
Prove earliest-end-first with the 'greedy stays ahead' argument, and refute earliest-start and shortest-first with counterexamples
Handle endpoint conventions correctly: >= for half-open intervals, > for closed ones
Cover a range with the fewest intervals using the farthest-reach greedy, detect gaps, and relate selection to minimum removals and stabbing points

Chapters

PreviousSort-and-Match Greedy NextSweep Line