Algorithms from zero
Greedy: a scheduler you can prove correct
Reading about greedy correctness is not the same as defending a greedy choice under review. Build a real interval scheduler, write the exchange argument that justifies it, then validate it against an exact DP oracle — and deliberately find a sibling problem where greedy is provably wrong, so you can feel the line between fast-and-correct and fast-and-wrong.
Turn the unit’s proof discipline into an engineering loop: pick a greedy rule, prove its first choice safe with an exchange argument, implement it in O(n log n), and validate it against a brute-force or DP oracle on randomized inputs — then locate and document a denomination/weighting where greedy fails and explain why no exchange closes.
Implement and validate a greedy interval scheduler that maximizes the number of non-overlapping intervals, prove its greedy choice safe with a written exchange argument, and contrast it with a sibling problem (weighted interval scheduling or a non-canonical coin set) where greedy is provably wrong and DP is required.
- The greedy scheduler matches the exact oracle on every one of >= 1000 randomized inputs, with the test harness and a fixed seed included so the run is reproducible.
- The written exchange argument explicitly states the feasibility fact (finish-time inequality) and the no-worse fact (one out, one in, count unchanged), plus the optimal-substructure recursion.
- For the sibling problem, a printed counterexample shows greedy and DP disagreeing, with both outputs and the input that triggers it.
- A short write-up names which problem has the greedy-choice property and which does not, and identifies the specific swap that fails in the unsafe case.
- Add the merge-intervals and minimum-rooms (meeting rooms II) variants and validate each against an independent oracle, confirming you used the correct sort key for each (start for merge, start-and-end sweep for rooms).
- Implement weighted interval scheduling with the O(n log n) DP (sort by finish, binary-search the last compatible interval) and show on a randomized suite that the unweighted greedy is wrong on it whenever the weights are non-uniform.
- Add a property-based test that generates adversarial interval sets (heavy nesting, many ties on finish time) and confirms greedy still matches the oracle, documenting how ties are handled by the exchange argument.
- Implement Gas Station and prove the reset-safety claim in code: assert that for every randomized feasible instance, the surviving start completes the loop with the tank never going negative, and that infeasible instances (total net < 0) return -1.
This is the loop you run whenever you reach for greedy in production: state the local rule, prove its first choice safe with an exchange argument (feasibility plus no-worse, then optimal substructure), implement it in one sorted pass, and validate against an exact oracle on randomized inputs before you trust it. The sibling counterexample is the other half of the discipline — feeling exactly where the swap fails is what stops you from shipping a fast algorithm that silently returns the wrong answer.