Advanced Greedy and Exchange Proofs

Interval scheduling variants, scheduling with deadlines, Huffman coding, matroid intuition, minimum spanning tree cut/cycle proofs, and examples where greedy fails.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Exchange argument for earliest-deadline-first: if an optimal schedule has two adjacent jobs out of deadline order, swapping them does not increase the maximum lateness; repeat until sorted.

Matroids: when the feasible sets form a matroid (independent sets closed under subsets, with the exchange property), “sort by weight and add an element whenever the set stays independent” is optimal. Forests in a graph form a matroid — which is why Kruskal works — and so do job sets that can meet their deadlines (the first program).

When greedy fails: 0/1 knapsack and non-canonical coin systems (Module 21) are not matroids; use DP.

#include <bits/stdc++.h>
using namespace std;

int main() {
    // unit-time jobs with deadlines and profits: maximise profit
    vector<pair<int, int>> jobs = {{2, 100}, {1, 19}, {2, 27}, {1, 25}, {3, 15}};   // deadline, profit
    // greedy: sort by deadline, keep a min-heap of chosen profits; drop the smallest if over capacity
    auto sorted = jobs; sort(sorted.begin(), sorted.end());
    priority_queue<int, vector<int>, greater<int>> chosen;
    for (auto [d, p] : sorted) { chosen.push(p); if ((int)chosen.size() > d) chosen.pop(); }
    long long greedy = 0; while (!chosen.empty()) { greedy += chosen.top(); chosen.pop(); }
    // brute force over all subsets: feasible if, sorted by deadline, the k-th job has deadline >= k
    long long best = 0; int n = (int)jobs.size();
    for (int mask = 0; mask < 1 << n; ++mask) {
        vector<int> ds; long long s = 0;
        for (int i = 0; i < n; ++i) if (mask >> i & 1) { ds.push_back(jobs[i].first); s += jobs[i].second; }
        sort(ds.begin(), ds.end()); bool ok = true;
        for (size_t k = 0; k < ds.size(); ++k) ok &= ds[k] >= (int)k + 1;
        if (ok) best = max(best, s);
    }
    cout << "job sequencing with deadlines: g
…

job sequencing with deadlines: greedy profit 142, brute force 142
maximum lateness: earliest-deadline-first 1, best of all 720 orders 1

Quiz

? Why is earliest-deadline-first optimal for minimising maximum lateness?
+ Swapping two adjacent out-of-order jobs never increases the maximum lateness (exchange argument). :: The run matched the best of all 720 orders.
- It finishes short jobs first :: Duration is not the criterion.
- It is a heuristic :: It is provably optimal.
- Deadlines are sorted in the input :: The algorithm sorts them.

? What property makes a greedy “add if still independent” algorithm optimal?
+ The feasible sets form a matroid :: Forests and schedulable job sets are matroids.
- The input is small :: No.
- All weights are distinct :: Helps uniqueness, not optimality.
- The sets are disjoint :: No.

? Which proof techniques justify greedy algorithms? (select all that apply)
+ Exchange argument :: Swap toward the greedy choice.
+ Staying ahead :: Greedy is never behind after each step.
+ Cut property :: For MSTs.
- Memoisation :: A DP technique.