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 18m 42s17 days 22 hours 18 minutes 42 seconds.

Advanced - Greedy and Scheduling · 3:57

Deadlines and Durations: Maximize Jobs Done

Each job has a duration and a deadline, runs without interruption, and counts only if it finishes on time. Scanning by deadline with a max-heap and dropping the longest job whenever the clock runs late (Moore–Hodgson) maximizes the count, and a backward sweep over the gaps between deadlines reaches the same answer. Unit tasks with profits use a latest-free-slot greedy instead, while durations and profits together are NP-hard.

You will learn

Maximize the number of on-time jobs by scanning in deadline order with a max-heap of durations and evicting the longest job when the clock passes the current deadline
Justify evicting the longest job with an exchange argument, and recognise the 'evict the newest' bug
Reconstruct an explicit schedule by running the kept jobs in deadline order, back to back, with a 64-bit clock
Solve unit-length tasks with profits by latest-free-slot placement (DSU) or a deadline sweep with a min-heap

Chapters

PreviousOne-Machine Scheduling: the Permutation Method NextTwo-Machine Flow Shop: Johnson's Rule