What Is the Activity Selection Problem? The Earliest-Finish-Wins Rule

You have one meeting room. Ten team leads, each convinced their weekly sync is the single most critical calendar event in the building. One room. One slot at a time. How many meetings can you actually fit in?

That's the activity selection problem. It's a classic greedy algorithm question and the direct prerequisite for every interval scheduling problem you'll encounter in a coding interview. The solution is elegant: always pick the activity that finishes earliest. The tricky part is understanding why that works, and why the two other orderings you'll instinctively reach for both fail.

One Room, Ten Requests

Formally: given a set of activities each with a start time and a finish time, select the largest subset where no two activities overlap.

Here's a concrete set:

Activity	Start	Finish
A	1	4
B	3	5
C	0	6
D	5	7
E	3	9
F	5	9
G	6	10
H	8	11
I	8	12
J	2	14

Two activities conflict if one starts before the other finishes. A (1 to 4) and B (3 to 5) conflict because B starts at 3 while A is still running. A and D (5 to 7) do not conflict because D starts exactly when A ends.

The optimal answer is A, D, H: three activities, no overlaps. You can't do better than three with this set. The question is how to find that without exhausting every possible subset.

Three Orderings. Two of Them Fail.

When you first see this problem, three orderings feel like natural candidates.

Sort by start time. Pick the activity that starts earliest. Makes intuitive sense. It's also completely wrong. Activity C starts at 0, so you pick it first. It runs until 6 and holds the room hostage. You end up with C and then G, and then the day is over. Two meetings instead of three.

Sort by duration. Pick the shortest activity first. Also broken. You can construct inputs where a short activity placed at the wrong spot blocks two longer non-overlapping ones that would've fit otherwise.

Sort by finish time. Pick the activity that ends soonest among those that don't conflict with what you've already selected. This is always optimal. By picking the activity that frees the room earliest, you leave the maximum time available for whatever comes next.

Sorting by finish time (left) vs. sorting by start time (right), as a visual.

Earliest Finish Is Always Safe

Here's the exchange argument, kept concrete. Suppose you have an optimal solution S that doesn't include X, the earliest-finishing activity. S must start with some other activity Y. Because X finishes earliest, X finishes no later than Y. Swap Y for X in S, and every activity that came after Y still fits. Nothing X blocks wasn't already blocked by Y. You get a valid solution of the same size, now containing X.

The earliest-finishing activity always belongs to some optimal solution. You can always include it without losing optimality. That's the greedy choice property: the locally greedy pick is globally safe.

After selecting X, cross off everything conflicting with it and repeat. No backtracking. No memoization. Just scan left to right and take what fits.

How It Runs

sort activities by finish time
select the first activity
last_finish = finish time of first activity

for each remaining activity in sorted order:
    if activity.start >= last_finish:
        select this activity
        last_finish = activity.finish

The condition is >=, not >. An activity that starts exactly when the previous one ends is fine. This trips people up more often than it should.

def activity_selection(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    activities.sort(key=lambda x: x[1])

    selected = [activities[0]]
    last_finish = activities[0][1]

    for start, finish in activities[1:]:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish

    return selected

function activitySelection(activities: [number, number][]): [number, number][] {
    activities.sort((a, b) => a[1] - b[1]);

    const selected: [number, number][] = [activities[0]];
    let lastFinish = activities[0][1];

    for (const [start, finish] of activities.slice(1)) {
        if (start >= lastFinish) {
            selected.push([start, finish]);
            lastFinish = finish;
        }
    }

    return selected;
}

Tracing through the example after sorting by finish time:

• A (1,4): selected. last_finish = 4
• B (3,5): 3 < 4, skip
• C (0,6): 0 < 4, skip
• D (5,7): 5 >= 4, selected. last_finish = 7
• E (3,9): 3 < 7, skip
• F (5,9): 5 < 7, skip
• G (6,10): 6 < 7, skip
• H (8,11): 8 >= 7, selected. Done.

Result: A, D, H.

O(n log n). That's the Sort.

Sorting dominates: the full algorithm runs in O(n log n). The sort costs O(n log n). The single left-to-right scan costs O(n). The actual decision logic is almost embarrassingly simple once the array is sorted. The whole algorithm is basically just "sort, then squint."

When you realize the entire complexity of this algorithm lives in one line: activities.sort(key=lambda x: x[1]).

If activities arrive pre-sorted by finish time, skip the sort and get O(n). Space is O(1) auxiliary. The only number you track between iterations is when the last selected activity ends.

How Interviews Reframe This

Coding interviews rarely hand you the textbook form. They dress it up and ask it sideways.

LeetCode 435: Non-overlapping Intervals. "Remove the minimum number of intervals so the rest don't overlap." Same sort by finish time, same greedy scan. Minimum removals = total minus the maximum non-overlapping count. Identical logic, different question.

LeetCode 252: Meeting Rooms. "Can one person attend all meetings?" Sort by start time, check if any two adjacent intervals overlap. Simpler, but the same interval intuition.

LeetCode 253: Meeting Rooms II. "What's the minimum number of rooms needed?" Related but different. Sort by start time, use a min-heap to track when each room frees up. You're assigning every activity to a room, not selecting a maximum subset.

The weighted variant. What if each activity has a profit and you want to maximize total profit? Greedy fails completely. A single high-value long activity might beat three short cheap ones, and earliest-finish ignores value. The weighted version requires dynamic programming: a DP table over activities sorted by finish time, with binary search to find the latest non-conflicting activity for each position. Yes, it's more work. No, there's no shortcut.

Activity Selection Problem vs. Merge Intervals

Both problems operate on intervals. Both benefit from sorting. The goal is different.

Merge intervals combines overlapping intervals into the fewest non-overlapping ones. Sort by start time, extend the current interval when there's overlap, emit it when there isn't.

Activity selection picks the largest subset with no overlap at all. Sort by finish time, select greedily.

When an interval problem shows up in your interview, ask first: am I combining overlapping intervals or selecting non-overlapping ones? The sort key and the scan logic both follow from that single question.

The Conference Room Rule

If the algorithm ever feels abstract, hold this analogy. You're booking one conference room for the day. Every request has a start and an end. You want as many meetings as possible.

The rule: always book the next meeting that starts after the room is free and ends the soonest. You don't care who submitted the request first. You don't care how long it runs. You don't care if the request came from a VP. You only care about when the room opens up again. Every time you pick the earliest-ending meeting, you guarantee the rest of the day stays as open as possible.

Nobody's optimizing for the meeting that feels important. You're optimizing for the entire day.

That mental model maps directly to every interval scheduling variant you'll encounter. If you want to practice reasoning through these problems out loud under real interview conditions, SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly this kind of problem.

Quick Reference

• Activity selection: pick the maximum number of non-overlapping intervals from a set.
• Sort by finish time. Not start time. Not duration.
• Earliest-finishing activity always belongs to some optimal solution (exchange argument).
• Time: O(n log n). Space: O(1) auxiliary.
• LeetCode 435 is the direct mapping: minimum removals = total minus maximum non-overlapping count.
• Weighted variant breaks greedy entirely. Switch to DP when activities have values.

Further Reading

• Activity Selection Problem (Wikipedia)
• Activity Selection Problem, Greedy Algorithm (GeeksforGeeks)
• Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms" (CLRS), 4th edition, Section 16.1
• LeetCode 435: Non-overlapping Intervals
• LeetCode 253: Meeting Rooms II