Greedy Algorithms Practice Test: Timed Exchange Proof Quiz
A timed 45-minute greedy practice test: exchange arguments, earliest finish, event sweeps and tie order, when greedy fails, and a tasks-and-deadlines problem.
- Course: Competitive Programming study plan
- Module: Greedy algorithms and exchange proofs
- Kind: Checkpoint — cleared at 70%
- Reading time: 45 min
- Runtime: Clang 18 · C++20
Checkpoint — Greedy algorithms and exchange proofs is the checkpoint that closes the Greedy algorithms and exchange proofs module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
A timed checkpoint on greedy algorithms: choosing a rule, proving it with an exchange argument, sweeping events with the right tie order and recognising when a problem needs DP instead.
How it works. Ten questions and one program, in 45 minutes from when you start the timer. Clear 70% of the questions and get the program accepted on every hidden case to complete the module.
Before you start, make sure you can answer these from memory:
- The exchange argument for activity selection, in two sentences.
- Why earliest start and shortest first fail for activity selection.
- How the tie order of events changes between inclusive and half-open intervals.
- A coin system where largest-coin-first is wrong, and what solves it.
- Why shortest-duration-first maximises the sum of deadline minus finish time.
Common questions
How do you order tasks to maximise the sum of deadline minus finish time?
Do the shortest tasks first. The deadlines add the same total in any order, so only the sum of finish times matters, and swapping an adjacent longer-then-shorter pair always lowers it. Sort by duration and accumulate in long long.
How do you test a greedy rule quickly?
Write a brute force that tries every order or subset for n up to about 8, run both on a few thousand random small inputs and compare. A wrong greedy usually fails within seconds, long before a contest penalty.
Exercise
Tasks and deadlines
You must do n tasks one after another, starting at time 0, in any order you choose. Task i takes a_i units of time and has deadline d_i. If it finishes at time f, you earn d_i − f points — negative when it is late. Print the largest total you can earn.
Input: n (1 ≤ n ≤ 2·10^5), then n lines a d (1 ≤ a, d ≤ 10^6). Output: one integer (possibly negative).
3
6 10
8 15
5 12prints
2The order 5, 6, 8 finishes at 5, 11, 19 and earns 7 − 1 − 4 = 2. Finish times add up past 10¹¹ on the hidden cases.
In this module: Greedy algorithms and exchange proofs
← Greedy algorithms — choose, then prove by exchange · The sieve, modular arithmetic and nCr mod p →