Activity Selection Problem

Table of Contents +

Imagine you have one room and a long list of events that all want to use it. A talk, a workshop, a meeting, a movie. Each one has a start time and an end time. Some of them clash. You cannot run two events in the same room at the same time. So you have to leave a few out. It sounds easy. But picking the most events that fit without any overlap is trickier than it looks.

That puzzle is the activity selection problem. It asks you to choose the largest set of activities that do not overlap in time. Each activity has a fixed start and end. In this tutorial we solve it with a greedy rule. The rule is short to write and surprisingly smart.

🎯 What the Problem Is Asking

You get a bunch of activities. Each activity has a start time and a finish time. Two activities clash if their times overlap. You want the biggest group of activities you can run one after another in the same room, with no clashing.

Here is the thing you should not do. You should not just grab the activity that starts first. You should not grab the shortest one either. Both of those feel right but they fail on some inputs. The trick is to look at when each activity finishes.

Let’s say we have these activities. Each one is a name with a start and an end.

Activity	Start	Finish
A	1	4
B	3	5
C	0	6
D	5	7
E	8	9

The best answer here is A, D, E. That is three activities and they never clash. We will see exactly how the greedy rule finds them.

💡 The Greedy Rule

The whole solution rests on one idea. Pick the activity that finishes earliest. Take it. Then throw away everything that clashes with it. Now look at what is left and do the same thing again. Keep going until nothing is left.

In short steps:

Always pick the next activity that finishes earliest and still fits.
Skip any activity that starts before your last picked one finishes.
Repeat until you run out of activities.

Why finishing earliest? Because the activity that ends soonest leaves the most time free for everyone else. Think about it. If your first event ends at 4, you have the whole day after 4 open for more events. If your first event ends at 6 instead, you just burned two extra hours for no reason. Picking the earliest finish keeps the room free as long as possible. More free room means more activities later.

🧠 Walking Through the Example

Let’s run the rule on our table. First we sort the activities by finish time, soonest first.

That order becomes: A (ends 4), B (ends 5), C (ends 6), D (ends 7), E (ends 9).

Now we go down the list and pick:

Pick A. It ends at 4. This is our first choice. Now nothing we pick can start before 4.
Look at B. B starts at 3. That is before 4, so B clashes. Skip it.
Look at C. C starts at 0. Also before 4. Clash. Skip it.
Look at D. D starts at 5. That is after 4, so it fits. Pick D. Now nothing can start before 7.
Look at E. E starts at 8. After 7, so it fits. Pick E.

We end with A, D, E. Three activities, zero clashes. That matches the best answer.

Tip

After you pick an activity, you only ever compare the next activity’s start time against your last picked activity’s finish time. If the start is greater than or equal to that finish, it fits. That single check is the heart of the algorithm.

🪜 Steps to Solve It

Before we write code, let’s pin down the exact steps. The order matters here.

Put all activities together with their start and finish times.
Sort the activities by finish time, smallest finish first.
Pick the first activity in the sorted list. Remember its finish time.
Walk through the rest of the list one by one.
For each activity, check if its start time is greater than or equal to the last picked finish time.
If yes, pick it and update the last picked finish time to this activity’s finish.
If no, skip it and move on.
When the list ends, the activities you picked are your answer.

💻 The Code

Now let’s turn those steps into real code. We keep each activity as a pair of start and finish. We sort the pairs by finish time. Then we loop once and greedily select. The code prints which activities it selected and how many. The sort is what makes the greedy choice work.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

def select_activities(acts):
    # Step 1: sort by finish time, smallest first.
    # Each activity is a tuple: (name, start, finish).
    acts.sort(key=lambda a: a[2])

    # Step 2: always pick the first activity after sorting.
    picked = [acts[0][0]]
    last_finish = acts[0][2]

    # Step 3: pick an activity only if it starts after the last finish.
    for name, start, finish in acts[1:]:
        if start >= last_finish:
            picked.append(name)
            last_finish = finish

    print("Selected:", " ".join(picked))
    print("Total activities:", len(picked))


activities = [
    ("A", 1, 4),
    ("B", 3, 5),
    ("C", 0, 6),
    ("D", 5, 7),
    ("E", 8, 9),
]
select_activities(activities)

The output of the above code will be:

Selected: A D E
Total activities: 3

Note

The slow part of this whole thing is the sort. Sorting the activities by finish time takes O(n log n) time. After that, the single loop that picks activities runs in O(n). So the total time is O(n log n). If the activities arrive already sorted by finish time, you can skip the sort and the rest is just O(n).

⏱️ Complexity at a Glance

Here is the cost of each part of the algorithm laid out together. The big number to remember is O(n log n).

Step	Time	Space
Sort by finish time	O(n log n)	O(1) to O(n)
Single greedy pass	O(n)	O(1)
Whole algorithm	O(n log n)	O(1) extra

Caution

A common mistake is to sort by start time instead of finish time. That breaks the greedy choice. Another mistake is using a strict greater-than check when comparing start and finish. If one activity finishes exactly when the next one starts, they do not clash. So use greater-than-or-equal so back-to-back activities are allowed.

🧩 What You’ve Learned

✅ The activity selection problem asks for the largest set of activities that do not overlap in time.
✅ The greedy rule is to always pick the activity that finishes earliest, then skip everything that clashes with it.
✅ Finishing earliest works because it leaves the most time free for the activities that come after.
✅ The algorithm is sort by finish time, then make one pass comparing each start against the last picked finish.
✅ Sorting costs O(n log n), the greedy pass costs O(n), so the whole thing is O(n log n).
✅ Use a greater-than-or-equal check so activities that touch end to end are both allowed.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Introduction to Greedy Algorithms
Fractional Knapsack

Previous Introduction to Greedy Algorithms Next Fractional Knapsack

Share & Connect

Share on LinkedIn