R6. Greedy Algorithms

What this lecture covers

This is a recitation session following the lecture on greedy algorithms, working through three practice problems with a teaching assistant rather than presenting new theory. It shows how to spot a greedy strategy for a new problem and how to prove that strategy correct using an exchange argument, complementing the cut-and-paste proofs from the main lecture.

Watching it gives you practice recognizing when sorting by a simple criterion (cost per unit, processing time, or start time) produces an optimal solution, and how to structure a short proof that swapping two out-of-order elements never makes things worse.

Key ideas

• Fractional 'metal blending' problem: given metals with different value-per-weight and limited supply of each, hit a target value with minimum total weight by using the most valuable metal first, then the next, until the target is met.
• Exchange argument: the standard proof technique used throughout — assume a solution uses a cheaper option instead of the best one, show substituting the best option strictly improves the result.
• Minimizing average completion time: given process run times, order them by increasing time so shorter jobs finish (and are counted) first; proved by showing any out-of-order pair ('inversion') can be swapped to reduce the total completion time.
• Completion time: for a sequence of processes, the completion time of a process is the sum of the run times of everything before and including it; the goal is to minimize the average of these completion times.
• Interval clone covering: given overlapping calendar events, find the minimum number of 'clones' (parallel resources) needed to attend every event, by sorting events by start time and assigning each to an existing clone if possible, otherwise creating a new one.
• Online scheduling: the shortest-job-first strategy extends to jobs arriving over time by re-sorting on remaining time (not total time) whenever a new job arrives, provided all jobs are equally weighted.

Walkthrough

Fractional metal blending (0:00)

The recitation opens with a problem of choosing weighted amounts of several metals, each with a different value per kilogram and a limited supply, to reach a target total value while minimizing total weight used. The greedy strategy is to sort metals by value per weight in decreasing order and use as much of the most valuable metal as available before moving to the next. The proof is a short exchange argument: substituting a more expensive metal for an equal value of a cheaper one always uses less weight.

Minimizing average completion time (5:02)

The second problem orders a set of processes to minimize their average completion time (the sum of run times up to and including each process, divided by the number of processes). The greedy rule is to sort by increasing run time. The proof considers a non-sorted sequence, finds an inversion (a longer process scheduled before a shorter one), and shows swapping them strictly decreases every completion time affected by the difference between the two run times, so any non-sorted order can be improved.

Interval clone covering (11:07)

The third problem asks how many 'clones' are needed to attend every event in an overlapping calendar. The strategy sorts events by start time and assigns each event to any existing clone whose schedule is free, creating a new clone only when none is available. The correctness argument shows that whenever a new clone is created, the starting event necessarily overlaps with one event already assigned to each existing clone, proving that many clones are unavoidable at that point in time.

Online scheduling extension (19:18)

The recitation closes by extending the completion-time problem to an online setting, where new jobs can arrive while others are running. The fix is to re-rank jobs by remaining time rather than original run time whenever a new job arrives, switching to a newly arrived job if it is now the shortest remaining task. This preserves optimality only under the assumption that all jobs carry equal weight or reward.

Before you watch

• Review the greedy choice property and cut-and-paste correctness proofs from the minimum spanning tree lecture, since this recitation reuses the same exchange-argument style of proof.
• Basic familiarity with sorting and interval scheduling problems is helpful background.

Check your understanding

1. In the metal-blending problem, why does sorting by value per weight and using the most valuable metal first minimize total weight used?
2. How does the inversion-swap argument prove that sorting processes by increasing run time minimizes average completion time?
3. Why does the interval clone problem require a new clone only when an event overlaps with something already assigned to every existing clone?
4. Why does the online scheduling extension require tracking remaining time rather than original run time once new jobs can arrive mid-execution?