Greedy Choice
Always pick the activity that finishes earliest and doesn't overlap with the last selected one. This leaves maximum room for future activities. Sort by end time first.
The Algorithm
sort by end time
select first activity
for each remaining activity:
if start >= lastEnd:
select it, update lastEnd
select first activity
for each remaining activity:
if start >= lastEnd:
select it, update lastEnd
Interactive Visualization
Considering Selected Rejected (Overlap)
| # | Start | End | Status |
|---|
Step 0 of 0
Considering
—
Last End
—
Selected
0
Total
0
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — Activity Selection
int activitySelection(vector<pair<int,int>>& acts) { sort(acts.begin(), acts.end(), [](auto& a, auto& b){ return a.second < b.second; }); int count = 1, lastEnd = acts[0].second; for (int i = 1; i < acts.size(); i++) { if (acts[i].first >= lastEnd) { count++; lastEnd = acts[i].second; } } return count; }
Complexity
Time
O(N log N)
Sorting dominates. Greedy pass is O(N).
Space
O(1)
In-place after sorting.