Activity Selection Problem
The Activity Selection problem asks for the maximum number of activities, each with a start and finish time, that one person can perform when they can only work on one activity at a time.
READY
A1
0–7
A2
1–4
A3
3–5
A4
4–8
A5
8–10
A6
9–12
Booked
0
Six activities, and they overlap. Book as many as will fit.
Next
Sort by earliest finish first. That order is the whole strategy.
Sort by
Intuition
Imagine you have a single meeting room and a list of requested meetings with start and end times. You want to accommodate as many meetings as possible. Intuition might say "pick the shortest meetings" or "pick the earliest starting meetings", but the correct greedy strategy is to always pick the meeting that finishes earliest. This leaves the maximum amount of time remaining for other meetings.
Concept
The Greedy Choice: Sort all activities by their finish time. Always pick the first available activity that doesn't overlap with the previously selected one.
This works because choosing the activity that finishes first leaves the resources free for the longest remaining time, maximizing the chance to fit in more activities.
How it Works
- Sort: Sort all activities based on their finish times in non-decreasing order.
- Select First: Always select the first activity (it finishes earliest).
- Iterate: For each remaining activity:
- If its start time is greater than or equal to the finish time of the last selected activity, select it.
- Otherwise, skip it (it overlaps).
Step-by-Step Breakdown
Consider activities (start, end): (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)
- Sort by End Time: This list is already in end-time order. (3,9) and (5,9) tie at 9; either order gives the same result.
- Select (1,4): It finishes first. (Last End = 4)
- Reject (3,5) and (0,6): They start at 3 and 0, before 4.
- Select (5,7): Start 5 is not before 4. (Last End = 7)
- Reject (3,9), (5,9) and (6,10): They start at 3, 5 and 6, before 7.
- Select (8,11): Start 8 is not before 7. (Last End = 11)
- Reject (8,12) and (2,14): They start at 8 and 2, before 11.
- Select (12,16): Start 12 is not before 11. (Last End = 16)
- Result: (1,4), (5,7), (8,11), (12,16): 4 activities, the maximum for this set.
Trace: six activities, sorted by finish time
sort
By finish time: A2 1–4, A3 3–5, A1 0–7, A4 4–8, A5 8–10, A6 9–12. A1 starts first but sorts third, because it runs until 7.
ends 4 5 7 8 10 12
keep A2
The first activity after the sort is selected outright: nothing finishes earlier. lastEnd = 4.
[A2] · lastEnd 4
A3 3–5
3 < 4: it starts while A2 is still running. Skip.
skip
A1 0–7
0 < 4. Its early start bought it nothing — it overlaps A2 as well.
skip
A4 4–8
4 >= 4. A4 starts the moment A2 ends, and the test is >=, so touching is not overlapping. Select it; lastEnd = 8.
[A2, A4] · lastEnd 8
A5 8–10
8 >= 8, the same boundary again. Select it; lastEnd = 10.
[A2, A4, A5] · lastEnd 10
A6 9–12
9 < 10: it overlaps A5. Skip. The loop ends and the selection is returned.
skip
why 3 is best
Take any largest schedule and its earliest-finishing activity. A2 finishes no later, so swapping A2 in clashes with nothing else in that schedule and keeps its size. Repeat on what starts at or after lastEnd, and the greedy picks match a largest schedule one for one. On this set no four activities are mutually disjoint, so 3 is the maximum.
3 = optimal
When to Use
- Scheduling meetings in a single room.
- Task scheduling on a single processor.
- Any interval problem where you want to maximize the count of non-overlapping intervals.
When NOT to Use
- If activities have different values or weights (use Weighted Interval Scheduling with DP).
- If multiple resources (rooms/machines) are available.
How to Identify
Keywords: "Maximum number of activities", "Non-overlapping intervals", "Single resource".
Applying for software engineering roles? Free, no sign-up: