Event Scheduling

Abstract

Suppose you are running a conference and you have a collection of events (or talks) that each have a start time and an end time. However, there is only one conference room available. Goal: schedule the most events possible that day such that no two events overlap.

• Category: Greedy Algorithm / Interval Scheduling
• Input: A collection of events, each with a start and finish time
• Output: A subset of events, none overlapping
• Paradigm: Greedy (Earliest End Time strategy)
• Typical use cases: room/resource booking, single-machine job scheduling, any “pick the max number of non-conflicting intervals” problem

---

Core Logic (High-Level)

Specification

• Instance: collection of events $(s_1,f_1),(s_2,f_2),\dots ,(s_n,f_n)$
• Solution Format: subset of events
• Constraints: no 2 events in the subset overlap
• Objective: cardinality of the subset ($\in \mathbb{R}$)
• Goal: maximize

Strategies to Solve

Before solving and proving a greedy algorithm, we should first find a greedy strategy to solve. Several candidate greedy strategies:

• Shortest duration ✘ — Counter Example: Solution $A$, Better Solution $B,C$.
• Earliest start time ✘ — Counter Example: Solution $A$, Better Solution $B,C,D$.
• Fewest conflicts ✘ — Solution: 3, Better Solution: 4.
• Earliest end time ✔ — Solution: 4 (optimal).

Key Idea

Picking the event that finishes soonest leaves the maximum possible remaining time for everything else — it’s the choice that constrains the future the least. That’s exactly why the other three strategies fail: shortest duration, earliest start, and fewest conflicts can all still “use up” time that a later, more useful event needed.

---

Pseudocode (Mid-Level Implementation)

Algorithm 43 Event Scheduling Implementation

procedure EventScheduling()

Initialize a Queue $S$

Sort the intervals by finish time

Put the first event $E_1$ in $S$

Set $F = f_1$

for $i = 2 \dots n$ do

if $s_i \geq F$ then

enqueue($E_i, S$)

$F = f_i$

return $S$

Variables & Data Structures

Name	Type	Purpose
S	Queue	Accumulates the chosen (non-overlapping) events, in order
F	Number	The finish time of the most recently accepted event — the earliest time the room becomes free next
E_i	Event $(s_i,f_i)$	The event currently being considered, in sorted order

Helper Functions / Operations Used

• Sort by finish time — a one-time $O(n\log n)$ pass that makes the rest of the algorithm a single linear scan
• enqueue(E_i, S) — accepts event $i$ into the schedule; $O(1)$

---

Proof of Correctness

We need to show: for every instance $I$, letting $GS$ be the greedy algorithm’s solution to $I$ and $OS$ be any other solution for $I$,

$$\underset{\text{Maximize}}{\underbrace{Value(OS)\le Value(GS)}}$$

(since this is a maximization problem — cardinality of the chosen subset).

The Tricky Part

$OS$ is an arbitrary solution, not one that makes sense to reason about directly — we don’t know much about it. This is what makes greedy optimality proofs harder than they first look, and why general techniques exist rather than ad hoc arguments each time.

Two of the three general techniques (see Techniques to Prove Optimality for the complete overview of all three) apply cleanly here, giving two independent proofs of the same result.

Proof via Exchange Argument

Let $E=E_1,\dots ,E_n$ be the set of all events, with $(s_i,f_i)$ the start and finish times of $E_i$​. Let $G$ be the event with the earliest finish time — the first greedy decision (include $G$). Let $OS$ be any non-overlapping schedule that does not include $G$.

Claim: there is a schedule $OS\prime$ that does include $G$ such that $|O{S}^{\prime }|\ge |OS|$.

Proof: let the events in $OS$ be $J_1,J_2,\dots ,J_k$, ordered by start and finish time ($J_1\ne G$).

Define $OS\prime$ from $OS$:

$$O{S}^{\prime }=(OS-\{J_1\})\cup \{G\}$$

$O{S}^{\prime }$ is valid (no overlapping events): since $OS$ is valid, no pair $J_i,J_{\ell }$​ overlaps — so it’s enough to show $G$ doesn’t overlap $J_2$ (the event right after $J_1$​). Since $OS$ is valid, $f_{J_1}<s_{J_2}$​​. And since $G$ is defined as the event with the earliest finish time overall, $f_G\le f_{J_1}<s_{J_2}$​​. So $G$ doesn’t overlap $J_2$​, and $O{S}^{\prime }$ is valid.

$|O{S}^{\prime }|\ge |OS|$: $O{S}^{\prime }$ removes exactly one event ($J_1$​) from $OS$ and adds exactly one ($G$) back in, so $|O{S}^{\prime }|=|OS|-1+1=|OS|$ — $O{S}^{\prime }$ is always at least as good (equal count), never worse.

Induction: this Exchange Argument claim alone doesn’t prove optimality — it needs an inductive argument on top. Prove by strong induction on nn n, the number of events:

• Base Case ($n=1$): any choice works, including the greedy choice.
• Inductive Hypothesis: suppose $n>1$, and the greedy algorithm is optimal for any $k$ events, $1\le k\le n-1$ — i.e. for $|I|<n$, $|OS(I)|\le |GS(I)|$ for any solution $OS(I)$.
• Inductive Step: let $OS$ be any solution on $I=\{E_1,\dots ,E_n\}$. By the Exchange Argument above, there’s a solution $O{S}^{\prime }$ with $|OS|\le |O{S}^{\prime }|$ that includes the first greedy choice $G$. Let $I^{\prime }$ be the events that don’t conflict with $G$, so $O{S}^{\prime }=\{G\}\cup S(I^{\prime })$ for some solution $S(I^{\prime })$ of $I^{\prime }$. Since $|I^{\prime }|<n$, the inductive hypothesis gives $|S(I^{\prime })|\le |GS(I^{\prime })|$. By definition, $GS(I)=\{G\}\cup GS(I^{\prime })$. Putting it together:

$$|OS(I^{\prime })|\le |O{S}^{\prime }(I)|=|\{G\}\cup S(I^{\prime })|\le |\{G\}\cup GS(I^{\prime })|=|GS(I)|$$

So the greedy algorithm is optimal for any $n$.

Proof via Greedy Stays Ahead

Consider input $I$ with $n$ events. Let $OS(I)=[J_1,\dots ,J_k]$ be an arbitrary set of non-conflicting events (in order), and let $GS(I)=[G_1,\dots ,G_{\ell }]$ be the greedy strategy’s output. Want to show: $k\le \ell$, i.e. $|GS(I)|\ge |OS(I)|$.

Compare a progress measure — when the $i^{th}$ event finishes.

Claim: $GS$ “stays ahead” of $OS$: $Finish(G_1)\le Finish(J_1)$ for all $i\ge 1$.

Proof (induction on $i$):

• Base Case: $Finish(G_1)\le Finish(J_1)$ by the greedy choice (earliest finish time overall).
• Inductive Hypothesis: for some $i\ge 1$, assume $Finish(G_i)\le Finish(J_i)$.
• Inductive Step: want $Finish(G_{i+1})\le Finish(J_{i+1})$. Among all events that start after $G_i$ finishes, $G_{i+1}$​ is chosen to be the one that ends earliest. Since $J_{i+1}$ starts after $J_i$ finishes (validity of $OS$), and $Finish(G_i)\le Finish(J_{i+1})\le Start(J_{i+1})$ (inductive hypothesis, then validity of $OS$), $J_{i+1}$ is a candidate the greedy strategy could have picked at step $i+1$ — and since greedy picks the earliest-finishing candidate, $Finish(G_{i+1})\le Finish(J_{i+1})$.

Using this to prove $k\le \ell$ (by contradiction): suppose $k>\ell$ (so $OS$ has more events than $GS$). Then $G_{\ell }$ is the last greedy choice, so no event starts after $G_{\ell }$​ finishes. By the Claim, $Finish(G_{\ell })\le Finish(J_{\ell })$, and by validity of $OS$, $Finish(J_{\ell })\le Start(J_{\ell +1})$. This implies there’s an event, $J_{\ell +1}$​ that starts after the last greedy choice finishes — but greedy would have picked it, contradicting that $G_{\ell }$​ was the last choice. So $k\le \ell$, meaning $|GS(I)|\ge |OS(I)|$.

Both proofs conclude the same thing — Earliest End Time is optimal — via genuinely different routes: Exchange inducts on shrinking the problem size, while Greedy Stays Ahead inducts on the sequence of choices itself. See Techniques to Prove Optimality for how these two techniques generalize beyond this example.

---

Time & Space Complexity Analysis

General Case

	Complexity	Notes
Time	$O(n\log n)$	Dominated by sorting the $n$ events by finish time; the single linear pass afterward is $O(n)$
Space	$O(n)$	Storage for the sorted event list plus the output queue $S$

Best / Worst / Average Case

• Best / Worst / Average case: All $O(n\log n)$ — sorting must happen regardless of how many events end up overlapping, and the linear scan afterward always touches every event once.

---

Drawbacks / Constraints

• The correct greedy criterion isn’t obvious. Three plausible-looking strategies (shortest duration, earliest start time, fewest conflicts) all fail — see the counterexamples above — which is exactly the general warning in Greedy Algorithms: a greedy algorithm needs a proof, not just intuition, before you can trust it.
• Not suitable for: weighted interval scheduling (maximizing total value of chosen events rather than just their count) — earliest-end-time is no longer guaranteed optimal once events have different weights; that variant requires Dynamic Programming instead.
• Preconditions: assumes a single resource (one conference room); scheduling across multiple identical rooms is a related but different problem (interval partitioning).

---

References / Links

• The Greedy Method
• Techniques to Prove Optimality
• Prove Kruskal’s with Exchange Argument
• Greedy Algorithms