Algorithm Guidecomplexity: O(n log n)

Activity Selection

A greedy problem where picking activities by earliest finish time lets you select the most non-overlapping activities. Sort by finish time, then adopt only the ones that don't overlap the previously chosen activity.

01Activity Selection

Explore How It Works

The activities sorted by earliest finish time. The goal is to pick as many as possible without overlapping in time.

Pick A(1~3), the one that finishes first. Anything next has to start at 3 or later.

B starts at 2, before A is over, so it overlaps. Skip it.

C starts at 4, so it doesn't overlap A. Pick it, and the bar moves to 6.

D starts exactly at 6. No overlap, so pick it and move the bar to 8.

E starts at 5, running into D before it ends. Skip it.

Selection complete · A · C · D, three of them. Picking the earliest-finishing first always guarantees the maximum count.

A (1~3)

B (2~5)

C (4~6)

D (6~8)

E (5~9)

012345678910

Live Python

1def activity_selection(activities):

2 activities.sort(key=lambda a: a[1]) # by finish time

3 selected = [activities[0]]

4 last_finish = activities[0][1]

5 for start, finish in activities[1:]:

6 if start >= last_finish: # if no overlap

7 selected.append((start, finish))

8 last_finish = finish

9 return selected

1 / 7

02 Understand It Simply

For Everyone

🔑How It Works

Choosing the activity that finishes earliest leaves the most room afterwards, which yields the largest possible count.

💡In Plain Words

Pick the activity that finishes earliest, then take only those that don't overlap your last pick.

That simple rule guarantees the maximum count.

📍Where It's Used

–Meeting-room and classroom assignment
–task scheduling

03 Python Implementation

A clean, readable reference implementation of the core logic of Activity Selection.

core_implementation.py

def activity_selection(activities):
    # activities: [(start, finish), ...]
    activities.sort(key=lambda a: a[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

04 Frequently Asked Questions

FAQ

What is Activity Selection?+

What is the time complexity of Activity Selection?+

The time complexity of Activity Selection is O(n log n). Follow the step-by-step visualization to see exactly why.

Where is Activity Selection used?+

Meeting-room and classroom assignment, task scheduling.

What's a simple analogy for Activity Selection?+

Choosing the activity that finishes earliest leaves the most room afterwards, which yields the largest possible count.

→ Greedy — see allRelated

🎯Coin Change (Greedy)

O(n)

🎯Huffman Coding

O(n log n)