Chapter 6. Greedy Algorithms

Each greedy algorithm in this chapter has a lattice-linear formulation: a state vector $G$, a forbidden predicate that detects local violations of the greedy invariant, and an advance rule that fixes them.

This page: LLP forms. View classical forms »

The LLP perspective

The four greedy algorithms in this chapter all admit lattice-linear reformulations on a state vector $G$. In each case the predicate $B$ pins down a unique target vector $G^\star$, the forbidden condition is $G[j] \prec G^\star[j]$ for the chapter's local order, and the advance step raises $G[j]$ to $G^\star[j]$. Several of the targets are prefix-structured, so the LLP advance step parallelizes directly via a parallel prefix scan: all forbidden indices read their targets from the same scan output and advance concurrently in a single logical round.

• LLP-IntervalScheduling. $G[j] \in \{\text{false}, \text{true}\}$ marks selected intervals. Forbidden when $G[j]$ is unselected and compatible with every already-selected earlier interval. Advance: $G[j] := \text{true}$.
• LLP-IntervalPartition. $G[j] \geq 1$ is the room assigned to course $j$. Forbidden when $j$ is unfixed but every overlapping earlier course is fixed. Advance: $G[j]$ to the least free room and mark $j$ fixed.
• LLP-MinMaxLateness. $G[j]$ is the start time of job $j$ (jobs are pre-sorted by deadline). Forbidden when $G[j] < \sum_{i < j} t[i]$. Advance: raise $G[j]$ to that prefix sum.
• LLP-FractionalKnapsack. $G[j] \in [0, 1]$ is the fraction of item $j$ taken (items pre-sorted by $v/w$ density). Forbidden when $G[j] < G^\star[j]$. Advance: $G[j] := G^\star[j]$.

LLP-IntervalScheduling

$G[j] = \text{true}$ marks selected intervals. Jobs sorted by finish time are held in a doubly linked list via $prev[\cdot]/next[\cdot]$; job $0$ starts selected. Index $j$ is forbidden when it is neither selected nor deleted and either (a) its current list-predecessor already finished by $s[j]$ — advance selects it, $G[j] := \text{true}$ — or (b) its predecessor is selected but still overlaps $j$ — advance deletes $j$ from the list in $O(1)$ via $next[prev[j]] := next[j];\ prev[next[j]] := prev[j]$. Sweeping $j$ in order of finish time matches the classical earliest-finish-time greedy.

Time complexity: $O(n)$ once intervals are sorted by finish time, $O(n \log n)$ overall, where $n$ is the number of intervals.

LLP-IntervalPartition

Each course $j$ is assigned a positive integer room $G[j]$, with overlapping courses getting distinct rooms. $\textit{pre}[j]$ is the set of earlier courses that overlap with $j$. Index $j$ is forbidden when every $i \in \textit{pre}[j]$ is fixed but $j$ is not; advancing assigns $G[j]$ to the least free room not used by any predecessor and marks $j$ fixed. The minimum number of rooms equals the maximum overlap depth.

Time complexity: $O(n \log n)$ via a min-heap of room finish times.

LLP-MinMaxLateness

Jobs are pre-sorted by deadline. $G[j]$ is the start time of job $j$ (initially $0$). $j$ is forbidden when $G[j] < \sum_{i < j} t[i]$; the advance lifts $G[j]$ to that prefix sum. After convergence, $\textit{lateness} = \max_j \max(0, G[j] + t[j] - d[j])$. Because every target is a prefix sum, all forbidden indices advance in a single logical round.

Time complexity: $O(n \log n)$ for the sort, $O(n)$ for the schedule, where $n$ is the number of jobs.

LLP-FractionalKnapsack

Items are pre-sorted by value-density $v/w$ in non-increasing order. Let $S_j = \sum_{k \leq j} w[k]$ be the cumulative weight. The target is $G^\star[j] = 1$ while $S_j \leq W$, the partial fraction at the breakpoint, and $0$ once $S_{j-1} \geq W$. Forbidden when $G[j] < G^\star[j]$; advance raises $G[j]$ to that value. All forbidden indices advance in a single logical round, driven by a prefix-sum scan over $w$.

Time complexity: $O(n \log n)$, where $n$ is the number of items.

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.

Looking ahead

The interval-scheduling and min-max-lateness ideas reappear in Chapter 7 (Shortest Paths) as the engine behind Dijkstra's algorithm: Dijkstra's "fix the closest unfixed vertex next" is exactly the greedy choice on the SSSP lattice. The exchange-argument template extends naturally to LLP correctness proofs.