Algorithm

Activity Selection

Greedy & Intervals Pattern

Activity Selection (Interval Scheduling)

You are given n activities, each with a start time and a finish time. A single person can work on only one activity at a time, so two activities conflict if their time ranges overlap. Return the maximum number of activities the person can complete. Two activities where one ends exactly when the other begins do not conflict and may both be chosen.

CONSTRAINTS
  • 1 ≤ n ≤ 10⁵
  • For each activity, start < finish
  • One activity at a time; ranges that overlap in their interior conflict
  • Touching at an endpoint (one finishes as the next starts) is allowed
EXAMPLE 1
Input: start = [1,3,0,5,8,5], finish = [2,4,6,7,9,9]
Output: 4
The activities (1,2), (3,4), (5,7) and (8,9) fit back-to-back without conflict. The activity (0,6) starts earliest but runs long, so keeping it would block more than it gains.
EXAMPLE 2
Input: start = [1,2,3], finish = [2,3,4]
Output: 3
Each activity ends exactly when the next begins, and touching at an endpoint is not a conflict, so all three fit.
EXAMPLE 3
Input: start = [1,1,1], finish = [3,3,3]
Output: 1
All three occupy the same range, so any two overlap and only one can be chosen.
EXAMPLE 4
Input: start = [0], finish = [10]
Output: 1
A single activity is always selectable on its own.
EXAMPLE 5
Input: start = [1,2,4], finish = [3,5,6]
Output: 2
Taking (1,3) then (4,6) gives two. The middle activity (2,5) overlaps both, so it cannot join a larger schedule.
If two activities touch at an endpoint, do they conflict?
No. An activity finishing at time t and another starting at time t can both be done, which is why the check is start ≥ last_finish rather than a strict greater-than. Confirm this boundary convention, since a strict version changes some answers.
Am I maximising the number of activities or the total busy time?
The number of activities. These are different goals — a single long activity can occupy more time than several short ones while counting as just one. If value or duration mattered, this would become a weighted problem needing dynamic programming.
Do I sort by start time or finish time?
Finish time. Sorting by start time leads to the wrong greedy, because an early start says nothing about how much future room an activity leaves. The whole correctness argument rests on finishing earliest.
Can activities have zero length or identical times?
The constraint here has start < finish, so no zero-length activities. Identical activities are allowed and simply conflict with one another, so at most one of a duplicate group is chosen.
The question, and why the obvious answers are wrong

You have a pile of activities, each occupying a time range, and you can only do one at a time. You want to do as many as possible. Note carefully what is being maximised: the count of activities, not the total time occupied, not the value of any single activity. A person who does five short talks beats a person who does one all-day workshop.

When several activities overlap and you can keep only one, which do you keep? The instinct is to reach for a rule, so let us test the tempting ones and watch them break — this is the discipline from the coin problem, applied again.

- Keep the one that starts earliest? No. The earliest-starting activity might run all day and block everything else. Start time tells you nothing about how much room it leaves behind.
- Keep the shortest one? Sounds efficient, but no. A short activity sitting in the middle of the timeline can straddle the boundary between two others and knock both out, when keeping those two would have been better.

Both failures share a cause: the thing that matters is not when an activity starts or how long it is, but when it frees you up again.

The safe greedy choice: finish earliest

Here is the choice that works: among all activities, do the one that finishes earliest. Then throw away everything that conflicts with it, and repeat on what remains.

The intuition is that finishing early is the most generous thing an activity can do for you — it hands back the most future time for everything else. But intuition is not proof, and greedy demands proof, so here is the actual argument.

Key Insightthe exchange argument for finishing first. Let f be the activity that finishes earliest of all. Claim: there is an optimal schedule that includes f. Take any optimal schedule, and look at its earliest-finishing activity, call it g. Since f finishes no later than g (it finishes earliest of everything), we can swap g out and f in. Does that break anything? Every other activity in the optimal schedule started after g finished, and f finishes no later than g, so all of them still start after f finishes — no new conflict is created. The swap keeps the same number of activities and now includes f. So an optimal schedule containing f exists, which means picking f is safe. Having picked it, the remaining problem — schedule everything that starts at or after f's finish — is the exact same problem on a smaller set, and the argument repeats.

That is the whole proof, and it is worth internalising, because it is the archetype for every interval greedy you will meet. The pattern: identify the choice, then show any optimal solution can be bent to include it without loss.

The algorithm

The proof hands us the algorithm directly. Sort by finish time; walk through, taking each activity whose start is not before the last taken activity's finish.

python
def max_activities(activities):
    # activities = [(start, finish), ...]
    activities.sort(key=lambda a: a[1])      # sort by FINISH time
    count = 0
    last_finish = float('-inf')
    for start, finish in activities:
        if start >= last_finish:             # no conflict with the last one kept
            count += 1
            last_finish = finish             # this activity now bounds the future
    return count

Sorting is O(N log N) and dominates; the scan is O(N). We only ever compare against last_finish, because once activities are sorted by finish time, the last one kept is guaranteed to be the earliest-freeing constraint on everything ahead.

Worked Example:starts = [1,3,0,5,8,5], finishes = [2,4,6,7,9,9]
Pair them and sort by finish: (1,2), (3,4), (0,6), (5,7), (8,9), (5,9).
- (1,2): start 1 ≥ −∞. Take it. Count 1, last_finish = 2.
- (3,4): start 3 ≥ 2. Take it. Count 2, last_finish = 4.
- (0,6): start 0 < 4. Conflict, skip. (It finishes late anyway — exactly the kind of greedy trap avoided.)
- (5,7): start 5 ≥ 4. Take it. Count 3, last_finish = 7.
- (8,9): start 8 ≥ 7. Take it. Count 4, last_finish = 9.
- (5,9): start 5 < 9. Conflict, skip.

Answer 4, the schedule (1,2), (3,4), (5,7), (8,9). Notice (0,6) was rejected despite starting first — the early start was a lure, and finishing-first was the safe guide.

The pattern, extracted

This is the foundational greedy on intervals, and its shape recurs constantly. The reusable recipe:

1. Sort by the right key. For "keep the most non-conflicting things", the key is finish time. Choosing the sort key is choosing the greedy, so spend your thinking here.
2. Sweep once, tracking a single boundary — the finish time of the last thing kept — and accept an item only if it clears that boundary.
3. Justify with an exchange argument before trusting it. If you cannot show any optimal solution can be bent to include your greedy choice, you do not yet have a solution.

Recognition signals for this exact pattern in an unseen problem: you are given intervals or (start, end) jobs; you want the maximum number that mutually avoid overlap, or equivalently the minimum number to delete so the rest are disjoint. Those two phrasings are the same problem — keeping the most is the mirror of removing the fewest — and "Non-overlapping Intervals" later in this section is precisely that mirror, solved with this identical sort-by-finish greedy.

A close cousin swaps the goal: if instead you wanted to cover a timeline with the fewest rooms or catch every interval with the fewest points, the sort key and the tracked boundary change, but the discipline — pick the safe choice, prove it by exchange — does not.

Interactive Strategy Visualization

Finish Line Greedy

0
1
2
3
4
5
Intervals (Sorted by End)
[1,2]
[2,3]
[1,3]
[3,4]
Goal: Remove minimum intervals to make the rest non-overlapping.
CORE LOGIC

Always prioritize the interval that ends first. This leaves the most remaining time for other activities.

REMOVAL RULE

If an interval starts before the previous finish line, it MUST be removed.

Exponential Try Every Subset
→
O(N log N) Time Greedy Sort by Finish