GreedyGreedy
Activity Selection (earliest finish first)
Pick the maximum number of mutually compatible activities by repeatedly taking the one that finishes earliest.
A
A
A
B
B
B
B
B
B
B
B
B
B
B
C
C
C
D
D
E
E
E
F
F
F
Activities (grid order)
| id | start | end | state |
|---|---|---|---|
| A | 1 | 4 | — |
| B | 0 | 11 | — |
| C | 4 | 7 | — |
| D | 6 | 8 | — |
| E | 7 | 10 | — |
| F | 11 | 14 | — |
1/186 activities compete for one room, drawn on a shared time axis: each row is one activity and its filled cells are the time units it occupies. Two activities clash exactly when their rows overlap vertically, and we want the largest set with no vertical overlap at all.
Interval under considerationTaken / keptRejected — it conflictsAlready decided
PseudocodeLearn Activity Selection →
1sort activities by finish time, earliest first2last = -infinity # finish time of the most recent activity taken3for (s, f) in sorted order:4 if s >= last: # compatible with everything taken so far5 take it; last = f6 else:7 skip it # it overlaps the activity we already hold8return the taken activitiesVariables
activities6
horizon14
Complexity
best O(n)
avg O(n log n)
worst O(n log n)
space O(1)
Speed