Activity Selection Problem

Imagine you have a single lecture hall and multiple classes want to use it. Each class has a fixed start and finish time. Your goal is to schedule as many non-overlapping classes as possible.

Formally: given n activities with start times s[i] and finish times f[i], select the maximum-size subset of mutually compatible activities (no two selected activities overlap).

The key insight is deceptively simple: always pick the activity that finishes earliest among those compatible with your current selection.

1. Sort activities by finish time
2. Select the first activity
3. For each remaining activity, if its start time is ≥ the finish time of the last selected activity, select it

This works because choosing the earliest-finishing activity leaves the most room for subsequent activities.

Watch the greedy algorithm in action. Activities are shown as bars on a timeline, sorted by finish time. The algorithm scans left to right, selecting compatible activities (green) and rejecting overlapping ones (red).

Greedy Choice Property: There exists an optimal solution that includes the activity with the earliest finish time. If an optimal solution doesn't include it, we can swap the first selected activity for the earliest-finishing one without reducing the total count.

Optimal Substructure: After selecting activity aₖ, the remaining problem (activities starting after aₖ finishes) is a smaller instance of the same problem.

The algorithm runs in O(n log n) time — dominated by the sorting step. The greedy scan itself is O(n).

Sorting takes O(n log n). The single-pass greedy scan is O(n). No extra data structures are needed beyond the selection set.

Try your own set of activities! Edit the start and finish times below and run the algorithm to see which activities get selected.