Activity Selection Problem

In the previous lesson, we introduced the greedy strategy and understood its core philosophy.

Now we apply that thinking to one of the most famous greedy problems — the Activity Selection Problem.

This problem clearly demonstrates how making the right local choice can lead to a globally optimal solution.

The Problem Statement

You are given a set of activities.

Each activity has:

• A start time
• A finish time

Only one activity can be performed at a time.

The goal is to select the maximum number of non-overlapping activities.

Real-World Interpretation

Imagine you are scheduling meetings in a single conference room.

Each meeting has a start and end time.

You want to conduct as many meetings as possible without any overlap.

This is exactly the Activity Selection Problem.

Why Greedy Works Here

The key greedy insight is simple:

Always select the activity that finishes earliest.

By finishing early, you leave more room for other activities afterward.

This greedy choice property guarantees an optimal solution.

Step-by-Step Greedy Strategy

The greedy algorithm follows this logic:

First, sort all activities by their finish times.

Select the activity with the earliest finish time.

Then, repeatedly select the next activity whose start time is greater than or equal to the finish time of the last selected activity.

Worked Example

Suppose we have the following activities:

Start times: (1, 3, 0, 5, 8, 5)
Finish times: (2, 4, 6, 7, 9, 9)

After sorting by finish time, the selected activities would be:

(1,2), (3,4), (5,7), (8,9)

This results in selecting 4 non-overlapping activities.

Pseudocode Explanation

sort activities by finish time

select first activity
last_finish = finish_time_of_selected

for each remaining activity:
    if activity.start >= last_finish:
        select activity
        last_finish = activity.finish

This algorithm runs efficiently and avoids unnecessary comparisons.

Time Complexity

Sorting the activities takes O(n log n).

Selecting activities takes O(n).

Overall complexity:

O(n log n)

Why Earliest Finish Time Matters

If we instead chose activities based on shortest duration or earliest start time, the result may not be optimal.

Only earliest finish time guarantees the greedy choice property.

Mini Practice

Think carefully:

• Why does finishing early allow more activities?
• What happens if two activities finish at the same time?

Exercises

Quick Quiz

The Activity Selection Problem is the foundation for many real-world scheduling systems.

In the next lesson, we will solve another classic greedy problem — the Fractional Knapsack Problem.