Course contentsShow
← Computer Science
Lesson 888 of 2,87221. Greedy AlgorithmsFree lesson

Activity Selection Problem

Select maximum non-overlapping activities from a set by always choosing the activity that finishes earliest.

Activity Selection Problem

You'll learn how to select the maximum number of non-overlapping activities by always choosing the one that finishes earliest.

The Core Idea

Imagine you're organizing your day and have a list of activities, each with a start and end time. You want to do as many activities as possible, but they can't overlap. How do you choose?

The Activity Selection Problem solves this by using a greedy strategy: always pick the activity that finishes first among the remaining choices. This leaves the most room for future activities.

Why "Finish First" Works

Think of it like booking a conference room. If you always choose the meeting that ends earliest, you free up the room sooner for other meetings. A meeting that runs late blocks more future possibilities.

The algorithm:

  1. Sort all activities by their finish time
  2. Select the first activity (finishes earliest)
  3. For each remaining activity, if its start time is after or equal to the last selected activity's finish time, select it
  4. Repeat until no activities remain

Example Walkthrough

Activities: [(1,3), (2,5), (4,7), (1,8), (5,9), (8,10)] (start, finish pairs)

After sorting by finish time: [(1,3), (2,5), (4,7), (1,8), (5,9), (8,10)]

  • Select (1,3) — finishes at 3
  • Skip (2,5) — starts at 2, overlaps
  • Skip (4,7) — starts at 4, overlaps
  • Skip (1,8) — starts at 1, overlaps
  • Select (5,9) — starts at 5 ≥ 3, no overlap
  • Select (8,10) — starts at 8 ≥ 9? No, but starts at 8, overlaps with 9... Wait: starts at 8, last finished at 9, so skip

Maximum activities: 2 or 3 depending on ties.

Key Takeaway: The Activity Selection Problem demonstrates greedy algorithms at their best—by always choosing the activity that finishes earliest, you maximize opportunities for future selections and guarantee an optimal solution.