Activity Selection Problem

The Activity Selection Problem asks: given a set of activities, each with a start time and a finish time, and a single resource that can only handle one activity at a time (a meeting room, a machine, a person’s calendar), what is the largest possible group of activities you can schedule so that no two overlap? It is one of the cleanest examples of a greedy algorithm: a simple, provably optimal rule — always pick the activity that finishes earliest among the ones still available — solves a problem that looks at first glance like it might need brute-force search. Understanding why this greedy rule works is more valuable than the code itself, because the same reasoning pattern (sort by a key, then scan once) shows up throughout greedy algorithm design.

Overview: How the Greedy Strategy Works

Suppose you have activities represented as (start, finish) pairs, and you want the maximum number of them that can run on a single shared resource without any two overlapping in time. Two activities are compatible if one finishes at or before the other starts — that is, activity A and activity B do not conflict when A’s finish time is less than or equal to B’s start time (or vice versa).

A tempting first idea is to greedily pick the shortest activity first, on the theory that short activities “use up” less of the schedule. Another tempting idea is to pick activities in order of their start time, since that feels like the natural reading order. Both of these are wrong, and the Common Mistakes section below shows concrete cases where each one fails. The rule that actually works is: sort all activities by finish time, then repeatedly pick the next activity whose start time is greater than or equal to the finish time of the last activity you picked.

Why does finishing earliest matter more than starting earliest or being short? Because the activity that finishes earliest leaves the most possible room in the schedule for everything that comes after it, no matter how long it lasted or when it began. Formally, this can be proven with an exchange argument: take any optimal schedule, and suppose its first activity is not the one with the globally earliest finish time. You can always swap it out for the activity that finishes earliest without ever making the schedule worse, because the earliest-finishing activity frees up at least as much room as whatever it replaces. Applying this swap repeatedly shows that some optimal solution always starts with the earliest-finishing activity — and by induction, the same argument applies to every subsequent choice. This is what makes the greedy choice not just simple, but provably correct, unlike many greedy-looking heuristics that only work sometimes.

The algorithm itself is short:

  1. Sort the activities by finish time, ascending.
  2. Select the first activity in this sorted order (it has the earliest finish time overall).
  3. Walk through the rest of the sorted activities. For each one, if its start time is greater than or equal to the finish time of the most recently selected activity, select it and update the “last finish time” to its finish time. Otherwise, skip it — it overlaps with something already chosen.

That single pass, after the sort, is all it takes to find the maximum number of mutually compatible activities.

Time and Space Complexity

Step Time Space Why
Sort activities by finish time O(n log n) O(n) Python’s sorted() uses Timsort, a comparison sort that is O(n log n) in the average and worst case; Timsort allocates working space proportional to the input.
Single greedy scan to select activities O(n) O(k), where k is the number selected (k <= n) Each activity is visited exactly once and compared against a single running value (the last finish time); the output list holds at most n entries.
Overall O(n log n) O(n) The sort dominates; the scan afterward is linear.

There is one useful special case: if the activities are already sorted by finish time — which happens often in practice, for example when reading events off a calendar API in chronological order of completion — you can skip the sort entirely and the whole algorithm runs in O(n) time and O(1) extra space (beyond the output). Timsort also detects already-sorted runs and finishes in close to O(n) on nearly-sorted input, but you only get that speed-up automatically if you actually call sorted() on data that is already ordered; it does not help if you sort by the wrong key.

Examples

Example 1: Basic activity selection

def activity_selection(start: list[int], finish: list[int]) -> list[int]:
    indices = sorted(range(len(start)), key=lambda i: finish[i])
    selected = [indices[0]]
    last_finish = finish[indices[0]]
    for i in indices[1:]:
        if start[i] >= last_finish:
            selected.append(i)
            last_finish = finish[i]
    return selected


start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]

selected = activity_selection(start, finish)
print(f"Selected activity indices: {selected}")
for i in selected:
    print(f"  Activity {i}: start={start[i]}, finish={finish[i]}")

Output:

Selected activity indices: [0, 1, 3, 4]
  Activity 0: start=1, finish=2
  Activity 1: start=3, finish=4
  Activity 3: start=5, finish=7
  Activity 4: start=8, finish=9

Here the six activities are already listed in non-decreasing order of finish time, so sorting doesn’t reorder anything. The scan picks activity 0 (finishes at 2), then activity 1 (starts at 3, which is at or after 2, so it’s compatible), then rejects activity 2 (starts at 0, before the last finish of 4), then accepts activity 3 (starts at 5, at or after 4), then accepts activity 4 (starts at 8, at or after 7). Activity 5 starts at 5, which is before the running finish time of 9, so it’s rejected. Four activities out of six make it into the final schedule.

Example 2: A realistic scheduling scenario

def select_meetings(meetings: list[tuple[str, float, float]]) -> list[tuple[str, float, float]]:
    sorted_meetings = sorted(meetings, key=lambda meeting: meeting[2])
    selected = [sorted_meetings[0]]
    for name, start, end in sorted_meetings[1:]:
        _, _, last_end = selected[-1]
        if start >= last_end:
            selected.append((name, start, end))
    return selected


meetings = [
    ("Standup", 9.0, 9.5),
    ("Design Review", 9.0, 10.0),
    ("1:1 with Manager", 9.5, 10.5),
    ("Sprint Planning", 10.0, 11.5),
    ("Lunch and Learn", 11.0, 12.0),
    ("Client Call", 11.5, 13.0),
]

schedule = select_meetings(meetings)
print(f"You can attend {len(schedule)} meetings back-to-back:")
for name, start, end in schedule:
    print(f"  {name}: {start} - {end}")

Output:

You can attend 3 meetings back-to-back:
  Standup: 9.0 - 9.5
  1:1 with Manager: 9.5 - 10.5
  Lunch and Learn: 11.0 - 12.0

This models a single person who wants to attend as many of six overlapping meetings as possible. Sorted by end time, “Standup” finishes earliest, so it’s picked first. “Design Review” also starts at 9.0 but finishes later than “Standup” already claimed the 9.0-9.5 slot, so it’s skipped. “1:1 with Manager” starts exactly at 9.5, which matches the running end time, so it’s compatible and picked. “Sprint Planning” starts at 10.0, before the new running end of 10.5, so it’s rejected. “Lunch and Learn” starts at 11.0, after 10.5, so it’s accepted. “Client Call” starts at 11.5, before the running end of 12.0, so it’s the last one rejected. Out of six candidate meetings, only three can actually be attended without conflict.

Example 3: Why finish time and not start time

def activity_selection_by_start(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    sorted_by_start = sorted(activities, key=lambda activity: activity[0])
    selected = [sorted_by_start[0]]
    for start, finish in sorted_by_start[1:]:
        if start >= selected[-1][1]:
            selected.append((start, finish))
    return selected


def activity_selection_by_finish(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    sorted_by_finish = sorted(activities, key=lambda activity: activity[1])
    selected = [sorted_by_finish[0]]
    for start, finish in sorted_by_finish[1:]:
        if start >= selected[-1][1]:
            selected.append((start, finish))
    return selected


activities = [(1, 10), (2, 3), (4, 5), (6, 7), (8, 9)]

by_start = activity_selection_by_start(activities)
by_finish = activity_selection_by_finish(activities)

print(f"Sorting by start time selects: {by_start} -> {len(by_start)} activities")
print(f"Sorting by finish time selects: {by_finish} -> {len(by_finish)} activities")

Output:

Sorting by start time selects: [(1, 10)] -> 1 activities
Sorting by finish time selects: [(2, 3), (4, 5), (6, 7), (8, 9)] -> 4 activities

The activity (1, 10) starts earliest of all, so sorting by start time picks it first — and because it spans the entire timeline, every other activity conflicts with it, leaving a schedule of just one activity. Sorting by finish time instead picks (2, 3) first, then successfully adds (4, 5), (6, 7), and (8, 9), for a schedule of four. This is the concrete proof that “earliest finish” is the right greedy key, not “earliest start.”

How It Works Step by Step

Tracing Example 1 (start = [1, 3, 0, 5, 8, 5], finish = [2, 4, 6, 7, 9, 9]) one step at a time, in finish-time order:

Step Activity considered (start, finish) Comparison Decision Running last finish
1 (1, 2) first activity, always taken Select 2
2 (3, 4) 3 >= 2 Select 4
3 (0, 6) 0 >= 4? No Reject 4
4 (5, 7) 5 >= 4 Select 7
5 (8, 9) 8 >= 7 Select 9
6 (5, 9) 5 >= 9? No Reject 9

Notice that the algorithm never backtracks or reconsiders a rejected activity, and it never needs to compare a candidate against anything but the single most recently accepted activity — that is what makes the scan O(n) after the sort.

Common Mistakes

Mistake 1: Greedily choosing the shortest activity instead of the earliest finish time

It seems intuitive that picking short activities first leaves more room for others, but this is not true in general. Consider a short activity sandwiched between two longer, mutually compatible ones:

def select_by_shortest_duration(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    sorted_by_duration = sorted(activities, key=lambda activity: activity[1] - activity[0])
    selected = [sorted_by_duration[0]]
    for start, finish in sorted_by_duration[1:]:
        if start >= selected[-1][1]:
            selected.append((start, finish))
    return selected


activities = [(1, 4), (3, 5), (4, 7)]
result = select_by_shortest_duration(activities)
print(f"Shortest-duration-first selects: {result} -> {len(result)} activities")

Output:

Shortest-duration-first selects: [(3, 5)] -> 1 activities

The activity (3, 5) has the shortest duration (2 units), so it’s picked first, but it overlaps both (1, 4) and (4, 7), blocking both of them and leaving a schedule of size 1. The correct approach sorts by finish time instead:

def select_by_finish_time(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    sorted_by_finish = sorted(activities, key=lambda activity: activity[1])
    selected = [sorted_by_finish[0]]
    for start, finish in sorted_by_finish[1:]:
        if start >= selected[-1][1]:
            selected.append((start, finish))
    return selected


activities = [(1, 4), (3, 5), (4, 7)]
result = select_by_finish_time(activities)
print(f"Finish-time-first selects: {result} -> {len(result)} activities")

Output:

Finish-time-first selects: [(1, 4), (4, 7)] -> 2 activities

Sorting by finish time correctly finds the schedule of two compatible activities, (1, 4) and (4, 7), that duration-based sorting missed.

Mistake 2: Using a strict > instead of >= when checking compatibility

Two back-to-back activities where one ends exactly when the next begins are compatible — a meeting ending at 4:00 and another starting at 4:00 do not overlap. A common off-by-one bug uses a strict greater-than comparison, which wrongly rejects this valid back-to-back case:

def select_activities_wrong(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    sorted_activities = sorted(activities, key=lambda activity: activity[1])
    selected = [sorted_activities[0]]
    for start, finish in sorted_activities[1:]:
        if start > selected[-1][1]:
            selected.append((start, finish))
    return selected


activities = [(1, 4), (4, 6), (6, 8)]
result = select_activities_wrong(activities)
print(result)

Output:

[(1, 4), (6, 8)]

The activity (4, 6) starts exactly when (1, 4) finishes, so it should be selected, but 4 > 4 is false, so it’s wrongly skipped, and the schedule loses one activity it should have kept. The fix is a one-character change, from a strict comparison to an inclusive one:

def select_activities_correct(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    sorted_activities = sorted(activities, key=lambda activity: activity[1])
    selected = [sorted_activities[0]]
    for start, finish in sorted_activities[1:]:
        if start >= selected[-1][1]:
            selected.append((start, finish))
    return selected


activities = [(1, 4), (4, 6), (6, 8)]
result = select_activities_correct(activities)
print(result)

Output:

[(1, 4), (4, 6), (6, 8)]

Whether the boundary should really be inclusive depends on the problem statement — some real scheduling systems require a buffer between activities, in which case a strict comparison (or an explicit gap) is actually correct. The mistake is not choosing one convention or the other; it’s not being deliberate about which one your code implements.

Best Practices

  • Always sort by finish time, never by start time or duration — those are the two most common wrong greedy keys for this problem.
  • Be explicit and consistent about whether back-to-back activities (one ending exactly when another starts) count as compatible; use >= if they do, > if your problem requires a strict gap.
  • If the input is already sorted by finish time (common when reading events in chronological completion order), skip the sort and do a single O(n) pass instead of paying for O(n log n) unnecessarily.
  • If you need to recover which activities were chosen (not just the count), sort a list of (start, finish) tuples or index positions directly, rather than sorting separate parallel arrays, to avoid bugs from indices getting out of sync.
  • Don’t reach for dynamic programming here — this greedy approach is provably optimal for the single-resource case in O(n log n), whereas a DP formulation would cost more time and space for no better answer.
  • If you actually need to schedule activities across multiple identical resources (for example, the minimum number of meeting rooms to fit all activities), that is a related but different problem that typically uses a min-heap of end times rather than this single-pass greedy scan.

Practice Exercises

  • Exercise 1 — Basic implementation. Given activities = [(1, 3), (2, 5), (4, 7), (1, 8), (5, 9), (8, 10)], write a function that returns the maximum-size list of non-overlapping activities. Hint: sort by finish time first. You should end up selecting 3 activities.
  • Exercise 2 — Count only, O(1) extra space. Modify the algorithm so it only returns the count of selected activities rather than the list itself, without changing its time complexity. This is a common interview follow-up to test whether you understand that the list itself isn’t necessary for the core logic.
  • Exercise 3 — Weighted twist (harder). Now suppose every activity has a value in addition to its start and finish time, and you want to maximize total value instead of the count of activities. Explain in a sentence or two why the simple “sort by finish time” greedy no longer guarantees an optimal answer here, and what technique (hint: dynamic programming with binary search over compatible predecessors) would be needed instead.

Summary

  • The Activity Selection Problem asks for the maximum number of mutually non-overlapping activities that a single resource can perform.
  • The correct greedy strategy is to sort activities by finish time and repeatedly pick the next one whose start time is at or after the finish time of the last activity picked.
  • This works because the earliest-finishing activity always leaves at least as much room for future choices as any alternative — an exchange argument proves the greedy choice is always safe.
  • Time complexity is O(n log n), dominated by the sort; the scan afterward is O(n). Space is O(n) for the sorted copy and output.
  • If the input already arrives sorted by finish time, the whole algorithm collapses to O(n) time and O(1) extra space.
  • Sorting by start time or by duration are the two classic wrong approaches — both can produce a strictly smaller schedule than the optimal one.
  • Be deliberate about whether your compatibility check uses >= (back-to-back activities allowed) or > (a strict gap required) — this is a frequent off-by-one source of bugs.