Greedy Algorithms

Interval Scheduling, Matroids, and Scheduling with Deadlines

The material for interval scheduling is borrowed largely from the presentation in Klienberg Tardos, Algorithm Design.

The presentation for matroids is based on Erickson's chapter on matroids in the textbook Algorithms.

Slides made in collaboration with Claude. All the cool bits are thanks to Claude, and blame me for oversights :)

The Scheduling Problem

Scenario: You manage a single resource (a room, a machine, a projector...)

You receive requests to use it during specific time intervals.

Two requests are compatible if they don't overlap.

Goal: Accept as many requests as possible!

Let's Try It!

Select compatible intervals

Click "New Problem" to generate intervals

Click on intervals to select them. Pick as many non-overlapping intervals as possible!

Formal Definition

Input: Set of requests $\{1, 2, \ldots, n\}$

Request $i$ has start time $s(i)$ and finish time $f(i)$

Compatible: Requests $i, j$ are compatible if $f(i) \leq s(j)$ or $f(j) \leq s(i)$

Goal: Find a maximum-size subset of mutually compatible requests

What Strategy Would You Try?

Let's brainstorm: what greedy rule could we use to select intervals?

Audience Suggestions

Suggestions will appear here...

How Should We Choose?

What greedy strategy should we use?

Approach: Earliest Start Time

Strategy: Always select the request with smallest $s(i)$.
Intuition: Start using the resource as quickly as possible.

Counterexample Builder

Start: End:

Build an instance where "Earliest Start" fails to find optimal.

← Back to Approaches

Approach: Shortest Interval

Strategy: Always select the request with smallest $f(i) - s(i)$.
Intuition: Get short jobs out of the way quickly.

Counterexample Builder

Start: End:

Build an instance where "Shortest Interval" fails to find optimal.

← Back to Approaches

Approach: Fewest Conflicts

Strategy: Select the interval overlapping with fewest others.
Intuition: Minimize the "damage" of each choice.

Counterexample Builder

Start: End:

Build an instance where "Fewest Conflicts" fails. (This one is trickier!)

← Back to Approaches

Approach: Earliest Finish Time

Strategy: Always select the request with smallest $f(i)$.
Intuition: Free up the resource as soon as possible!

Counterexample Builder

Start: End:

Build an instance where "Earliest Finish" fails to find optimal.

The Algorithm

Let R = set of all requests, A = ∅

While R is not empty:
    Choose request $i \in R$ with smallest $f(i)$
    Add $i$ to A
    Remove all requests incompatible with $i$ from R

Return A

Running time: $O(n \log n)$ — just sort by finish time!

Why Does It Work?

We prove greedy "stays ahead" of any other solution.

Setup:

Let $i_1, i_2, \ldots, i_k$ be greedy's choices (in order)

Let $j_1, j_2, \ldots, j_m$ be any optimal solution (sorted)

Goal: Show that $k = m$

Greedy Stays Ahead

Lemma: For all $r \leq k$: $f(i_r) \leq f(j_r)$
Greedy's r-th interval finishes no later than optimal's r-th.

Proof by induction:

Base case ($r=1$): Greedy picks the interval with earliest finish time.

So $f(i_1) \leq f(j_1)$ for any other interval $j_1$. ✓

Greedy Stays Ahead (Induction Step)

Lemma: For all $r \leq k$: $f(i_r) \leq f(j_r)$
Greedy's r-th interval finishes no later than optimal's r-th.

Proof by induction:

Assume: $f(i_{r-1}) \leq f(j_{r-1})$ (induction hypothesis)

1. Since $j_r$ is compatible with $j_{r-1}$: $f(j_{r-1}) \leq s(j_r)$

2. By transitivity: $f(i_{r-1}) \leq s(j_r)$ → $j_r$ is available to greedy!

3. Greedy picks earliest finish in available zone → $f(i_r) \leq f(j_r)$ ✓

Greedy is Optimal

Theorem: The greedy algorithm returns an optimal set.

Proof by contradiction:

Suppose optimal has more: $m > k$
By "stays ahead": $f(i_k) \leq f(j_k)$
Since $m > k$, there exists $j_{k+1}$ starting after $j_k$ ends
So $j_{k+1}$ starts after $i_k$ ends — it was available!
But greedy stopped. Contradiction!

Beyond Interval Scheduling

Can we identify when greedy algorithms work in general?

Goal: Find a structural property of optimization problems that guarantees greedy success.

Setup:

• A finite universe $\mathbf{U} = \{e_1, e_2, \ldots, e_n\}$

• A weight function $w: \mathbf{U} \to \mathbb{Q}_{\geq 0}$

• A family $\mathcal{F} = \{S_1, \ldots, S_m\}$ of feasible subsets

Weight of a set: $w(S) = \sum_{e \in S} w(e)$

Goal: Find maximum weight set in $\mathcal{F}$

Note: $m$ can be exponential in $n$!
Access $\mathcal{F}$ via oracle: "Is $S \in \mathcal{F}$?"

A Natural Greedy Approach

Sort elements by weight: $w(e_1) \geq w(e_2) \geq \cdots \geq w(e_n)$

Let X = ∅

For i = 1 to n:
If X ∪ {eᵢ} ∈ $\mathcal{F}$:
X = X ∪ {eᵢ}

Return X

This looks like Kruskal's algorithm for maximum spanning trees!

Greedy Can Fail

Counterexample:

$\mathbf{U} = \{p, q, r\}$

$w(p) = 40, \quad w(q) = 30, \quad w(r) = 20$

$\mathcal{F} = \{\{p\}, \{q, r\}\}$

Greedy: Picks $\{p\}$ → weight 40

Optimal: $\{q, r\}$ → weight 50

Greedy is suboptimal!

Visualizing the Exchange Argument

Greedy choices $g_1, \ldots, g_k$ vs Optimal choices $o_1, \ldots, o_\ell$ (sorted by weight)

$T$

$g_1$

$g_2$

…

$g_{i-1}$

$g_i$

…

$g_{k-1}$

$g_k$

$|T| = i-1$ $\geqslant$ $\geqslant$ $\geqslant$ $<$ $|S| > |T|$ $S$

$o_1$

$o_2$

…

$o_{i-1}$

$o_i$

…

$o_{\ell-1}$

$o_\ell$

$|S| = i$

At position $i$: greedy chose $g_i$ but optimal has heavier $o_i$.

Exchange Property: If $S, T \in \mathcal{F}$ and $|S| > |T|$, then $\exists e \in S \setminus T$ such that $T \cup \{e\} \in \mathcal{F}$.

Toward a Definition

What property of $\mathcal{F}$ makes greedy work?

Nice Family:

If $S, T \in \mathcal{F}$ and $|S| > |T|$,

then $\exists e \in S \setminus T$ with $T \cup \{e\} \in \mathcal{F}$

Counterexample:

$\mathbf{U} = \{p, q\}$, $w(p) = 40$, $w(q) = 30$

$\mathcal{F} = \{\{p, q\}\}$

Greedy picks $\emptyset$ (weight 0), but optimal is $\{p,q\}$ (weight 70)!

Issue: Greedy's intermediate sets may not be in $\mathcal{F}$.

The Missing Ingredient

We need greedy's partial solutions to always be in $\mathcal{F}$.

Hereditary Property:

If $S \in \mathcal{F}$ and $T \subseteq S$, then $T \in \mathcal{F}$.

"Subsets of feasible sets are feasible."

Combined with exchange, this gives the right structure!

Matroid: The Definition

A matroid $\mathcal{M} = (U, \mathcal{F})$ consists of:

• A finite ground set $U$

• A collection $\mathcal{F}$ of subsets satisfying:

Non-emptiness: $\emptyset \in \mathcal{F}$
Heredity: If $S \in \mathcal{F}$ and $T \subseteq S$, then $T \in \mathcal{F}$
Exchange: If $S, T \in \mathcal{F}$ with $|S| > |T|$,
then $\exists e \in S \setminus T$ with $T \cup \{e\} \in \mathcal{F}$

Matroid Terminology

Independent set	A set in $\mathcal{F}$
Dependent set	A subset of $U$ not in $\mathcal{F}$
Basis	Maximal independent set
Rank	Size of any basis (all bases have same size!)
Circuit	Minimal dependent set

Example: Uniform Matroid

Uniform matroid $U_{k,n}$:

Ground set: $\{1, 2, \ldots, n\}$

Independent sets: $X$ is independent iff $|X| \leq k$

Bases: All subsets of size exactly $k$
Rank: $k$
Circuits: All subsets of size $k+1$

Special case: $U_{n,n}$ = free matroid (all subsets independent)

Example: Graphic Matroid

Graphic matroid $M(G)$ for graph $G = (V, E)$:

Ground set: Edge set $E$

Independent sets: Acyclic subgraphs (forests)

Bases: Spanning trees
Rank: $|V| - 1$ (for connected $G$)
Circuits: Cycles

Kruskal's algorithm = greedy on graphic matroid!

Exchange Property: Graphic Matroid

Graph Arena

Draw mode: Click to add nodes. Drag between nodes to add edges. Right-click to delete. Drag nodes to reposition.

More Matroid Examples

Cographic Matroid $M^*(G)$:
$I \subseteq E$ independent iff $(V, E \setminus I)$ is connected
Bases = complements of spanning trees

Matching Matroid:
$I \subseteq V$ independent iff a matching covers all of $I$

Disjoint Path Matroid:
For digraph with source $s$: $I \subseteq V$ independent iff
edge-disjoint paths exist from $s$ to each vertex in $I$

The Main Theorem

Theorem: For any matroid $\mathcal{M} = (U, \mathcal{F})$ and any weight function $w$, the greedy algorithm returns a maximum-weight basis.

Recall the algorithm:

Sort by weight (descending)
X = ∅
For each element e: if X ∪ {e} ∈ $\mathcal{F}$, add e to X
Return X

Proof Strategy

Let greedy output $G = \{g_1, g_2, \ldots, g_k\}$ (in order added)

Let $O = \{o_1, o_2, \ldots, o_m\}$ be an optimal basis (sorted by weight)

Claim: For all $i$: $w(g_i) \geq w(o_i)$

Greedy's i-th choice is at least as heavy as optimal's i-th.

Since all bases have the same size ($k = m$), this implies:

$w(G) = \sum w(g_i) \geq \sum w(o_i) = w(O)$

Proof of Claim

Suppose not: Let $i$ be the first index where $w(g_i) < w(o_i)$.

Consider:

$T = \{g_1, \ldots, g_{i-1}\}$ — greedy's first $i-1$ choices

$S = \{o_1, \ldots, o_i\}$ — optimal's first $i$ elements

Note: $|S| = i > i-1 = |T|$, and both $S, T \in \mathcal{F}$ (heredity)

By exchange: $\exists o_j \in S \setminus T$ with $T \cup \{o_j\} \in \mathcal{F}$

Proof (Continued)

We have $o_j \in S \setminus T$ with $T \cup \{o_j\} \in \mathcal{F}$.

Key observation:

• $o_j \in \{o_1, \ldots, o_i\}$, so $w(o_j) \geq w(o_i)$

• We assumed $w(o_i) > w(g_i)$

• So $w(o_j) > w(g_i)$

Contradiction!
Greedy considers elements in decreasing weight order.
When greedy chose $g_i$, it should have chosen $o_j$ instead (heavier and feasible)!

The Converse

Theorem: For any subset system $\mathcal{S}$ that is not a matroid, there is a weight function $w$ such that greedy does not return a maximum-weight set in $\mathcal{S}$.

Proof: If $\mathcal{S}$ is not heriditary, then let $S$ be any subset in $\mathcal{S}$ which is such that there exists $T \subset S$ and $T \notin \mathcal{S}$. Assign:

Give every element in $T$ a weight of 100.
Give every element in $S \setminus T$ a weight of 1.
Give every element not in $S$ a weight of 0.

Then $S$ is the unique optimal solution, but greedy will never find this set.

Let $X$ and $Y$ be two sets in $\mathcal{S}$ that violate the exchange property: $|X| > |Y|$, but for any $x \in X \setminus Y$, the set $Y \cup \{x\} \notin \mathcal{S}$.

Let $m = |Y|$.

Every element of $Y$ has weight $m + 2$
Every element of $X \setminus Y$ has weight $m + 1$
Every other element has weight zero

Greedy accepts all of $Y$, rejects all of $X \setminus Y$ (infeasible), then considers other elements.
Greedy returns weight $m(m+2) = m^2 + 2m$.
But $X$ has weight at least $(m+1)^2 = m^2 + 2m + 1$. Contradiction!

Scheduling with Deadlines

Scenario: You have $n$ tasks to complete in $n$ days.

Each task requires one full day of attention.

Each task has a deadline $d_i$ and a penalty $p_i$.

If task $i$ is completed after day $d_i$, you pay penalty $p_i$.

Goal: Schedule tasks to minimize total penalty!

Example

Task	Deadline	Penalty
A	2	5
B	1	3
C	2	7

Schedule [B, C, A]: B on day 1 ✓, C on day 2 ✓, A on day 3 ✗

Penalty = 5 (only A is late)

Schedule [A, C, B]: A on day 1 ✓, C on day 2 ✓, B on day 3 ✗

Penalty = 3 (only B is late) — Better!

Try It: Scheduling with Deadlines

Drag tasks to schedule them

Total Penalty: 0 | On-time tasks: - | Late tasks: -

Key Insight: Realistic Sets

Observation: The cost of a schedule is determined by which tasks are on time.

Definition: A set $X$ of tasks is realistic if there exists a schedule where every task in $X$ is on time.

Lemma: $X$ is realistic if and only if $|X(t)| \leq t$ for every $t$,

where $X(t) = \{i \in X : d_i \leq t\}$ (tasks with deadline ≤ t)

Intuition: Can't schedule more than $t$ tasks with deadline $\leq t$.

The Matroid Structure

Theorem: The collection of realistic sets forms a matroid.

Non-emptiness: ∅ is realistic ✓
Heredity: Subset of realistic set is realistic ✓
Exchange: If |X| > |Y| both realistic, can add some task from X to Y ✓

Rephrased goal: Find a realistic set $X$ maximizing $\sum_{i \in X} p_i$

(Maximize penalty of on-time tasks = minimize penalty of late tasks)

Greedy Algorithm

GreedySchedule(tasks):

Sort tasks by penalty (decreasing)

onTime ← ∅

for each task i:

if onTime ∪ {i} is realistic:

add i to onTime

return canonical schedule for onTime

Canonical schedule: Execute on-time tasks in deadline order, then late tasks.

Running time: $O(n^2)$, or $O(n \log n)$ with clever data structures.

Independent set	A set in \(\mathcal{F}\)
Dependent set	A subset of \(U\) not in \(\mathcal{F}\)
Basis	Maximal independent set
Rank	Size of any basis (all bases have same size!)
Circuit	Minimal dependent set