Unit 4.4 · about 4 h
116 / 324Greedy counterexamples and interval scheduling
Interval scheduling is the rare greedy proof you can carry in your head. Counterexamples are the tool that stops the wrong greedy rule before it ships.
- derive
- implement
You can now
- Construct a minimal counterexample that separates two plausible greedy rules on the same problem.
- Prove earliest-finish interval scheduling with the exchange argument and state its \(O(n \log n)\) time and \(O(1)\) extra space.
- Implement earliest-finish from the comparator contract and differentially test it against brute force on small inputs with pytest.
Covers
- Minimal counterexamples to plausible greedy rules
- Interval, scheduling and covering problems
Study, in this order
3 steps
- Interval scheduling: the comparator is the algorithmDSA Handbook - recursion, backtracking and greedy
Why the obvious approach finds the wrong answer; Why sort-by-end is optimal; Worked example: LC 435 on
[[1,2], [2,3], [3,4], [1,3]]; Sort-by-start, fold while overlapping (LC 56) - Greedy thinking: the failure halfDSA Handbook - recursion, backtracking and greedy
Where greedy fails, with coins
[1, 3, 4]and the decision ruleDepth · Read only the failure section and the decision rule. The proof templates were covered in the previous unit.
- Scheduling Classes, Section 4.2Algorithms - recursion, backtracking and greedy
4.2 Scheduling Classes (printed pp. 161-164): the earliest-finish rule and its exchange argument
Focus on
- The comparator is the algorithm: sort by end time, keep an interval exactly when its \(\text{start}\) is at least the \(\text{current end}\). Touching intervals are allowed in LC 435.
- The exchange step replaces the optimal first interval with the earliest-finishing one: it ends no later, so the rest stays disjoint, and induction finishes the proof.
- Sort-by-start fails on nesting:
[[1, 100], [2, 3], [3, 4]]keeps the long interval and removes 2, while the optimum keeps the two short ones and removes 1. - LC 435 and LC 56 differ at the boundary: LC 435 treats touching intervals as disjoint (overlap means \(\text{start} < \text{end}\)), while LC 56 merges them (\(\text{start} \le \text{end}\), then extend with
max). Pasting one boundary into the other is the standard bug.
Reproduce closed-book
[[1, 2], [2, 3], [3, 4], [1, 3]] returns 1 removal. A pytest loop over 500 small instances from random.Random(7) agrees with the brute-force maximum on all 500 cases.Traps
- Sorting by start or by duration. Start order fails on nesting (
[[1, 100], [2, 3], [3, 4]]); shortest-first fails when a short interval straddles two disjoint ones ([[1, 5], [4, 7], [6, 10]]keeps 1 against 2). Friendly samples pass both, so the test family needs both shapes. - Treating touching intervals as overlapping in LC 435.
[[1, 4], [4, 5]]removes nothing under LC 435 but merges under LC 56; the two problems also sort differently, by end and by start. - Trusting sample tests for a greedy rule. Shrink each candidate rule against the others until the smallest input where they disagree, and check nested and touching cases first.
Practice
LeetCode 435: Non-overlapping Intervals
Examples: [[1, 2], [2, 3], [3, 4], [1, 3]] returns 1; [[1, 2], [1, 2], [1, 2]] returns 2.
After submitting, read the DSA Handbook interval-scheduling chapter and the AlgoMaster Non-overlapping Intervals lesson (https://algomaster.io/learn/dsa/non-overlapping-intervals), and confirm your sort key and boundary match theirs.
Self-test
-
Give the earliest-finish exchange step in one move.
Let \(g_1\) be the earliest-finishing interval and \(o_1\) the first interval of an optimal set. \(o_1\) ends no earlier than \(g_1\), so replacing \(o_1\) with \(g_1\) keeps the set disjoint and no smaller; induct on the rest. -
Give the minimal counterexample to sort-by-start for maximum non-overlapping intervals.
[[1, 100], [2, 3], [3, 4]]. Start order keeps[1, 100]and removes 2. The optimum keeps[2, 3]and[3, 4]and removes 1. -
What does
[[1, 4], [4, 5]]give under LC 435 and under LC 56?LC 435 removes 0 because touching is allowed. LC 56 merges to[1, 5]. The overlap tests differ only at equality. -
How do you hunt a counterexample to a new greedy rule?
Shrink to the smallest input where two candidate rules disagree, trying nested, touching, and equal-endpoint cases first. A rule that survives only sorted samples is not proved.
Completion criterion
Stop when
LC 435 is accepted, and your differential test plus a nested-interval case both pass.
Mark passed, then open 4.5 Only mark this when you can do it without notes.Leads to
- 2.8 Interval ordering, merging and sweep lines Merging, sweep lines, and room-booking variants that need more than earliest-finish.
- 3.7 Minimum spanning trees with Kruskal and Prim The cut argument is the next exchange proof.
Comes after
- 2.8 Interval ordering, merging and sweep linesInterval scheduling proofs build on the merging order established here.
- 4.3 Greedy choice, optimal substructure and exchange argumentsPractice refuting plausible greedy rules, then prove earliest-finish scheduling.
Resources for this unit
- DSA Handbook - recursion, backtracking and greedy Study Part 7, Part 10 and the relevant foundations on recursion and probability. Write the state definition or greedy claim before opening code.
- Algorithms - recursion, backtracking and greedy Use the recursion, backtracking, divide-and-conquer and greedy chapters for recurrence derivations, proof templates and counterexamples.
Also in this section
- AlgoMaster DSA - decomposition and greedy slice Attempt N-Queens and Gas Station cold, then implement reservoir sampling and test its output distribution over fixed-seed trials. Add another judged problem only for a diagnosed weakness.
- MIT 6.042J - probability and randomized algorithms Use the probability, expectation and concentration readings to derive sampling probabilities and distinguish expected from high-probability guarantees.
- Algorithms lecture notes - randomized algorithms Use note 1 Discrete Probability, note 2 Nuts and Bolts (randomized quicksort, with QuickSelect in its exercises), note 4 Tail Inequalities and note 5 Hashing to derive expected costs, separate expected from high-probability guarantees, and analyze hashing behavior.