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

Activity Selection Problem

Master the classic greedy problem: selecting maximum non-overlapping activities by earliest finish time.

Activity Selection Problem

You'll learn how to maximize the number of non-overlapping activities using a greedy approach.

The Problem

Imagine you're managing a single conference room with multiple meeting requests, each with a start and end time. You can only host one meeting at a time, and meetings can't overlap. How do you select the maximum number of meetings possible?

This is the Activity Selection Problem, a classic greedy algorithm challenge.

The Greedy Strategy

Here's the key insight: always pick the activity that finishes earliest among remaining activities.

Why? By choosing the meeting that ends soonest, you free up the room as quickly as possible, leaving maximum opportunity for future meetings. This locally optimal choice (picking the earliest finish) leads to a globally optimal solution.

How It Works

  1. Sort all activities by their finish time (earliest first)
  2. Select the first activity (it finishes earliest)
  3. For each remaining activity:
    • If its start time is ≥ the finish time of the last selected activity, select it
    • Otherwise, skip it (it overlaps)

Why It's Greedy

You make the best immediate choice (earliest finish) without reconsidering. Unlike dynamic programming, you don't explore all possibilities—you commit to each decision based on a simple rule.

The greedy choice property holds because no other choice at any step produces a better outcome. Optimal substructure exists because after selecting an activity, the remaining problem is just another activity selection problem with fewer activities.

Key Takeaway: The Activity Selection Problem demonstrates greedy algorithms at their best—sort by finish time, then greedily select non-overlapping activities from earliest to latest for maximum count.