Activity Selection Problem

Problem Statement

Given N activities, each with a start time and finish time, select the maximum number of non-overlapping activities. Two activities conflict if one starts before the other finishes. You can perform only one activity at a time.

Real-World Analogy

You are a conference room manager. Multiple teams want to book the room today. Each request has a start and end time. You want to accommodate as many meetings as possible. The greedy insight: always approve the meeting that ends earliest — it frees the room soonest for the next meeting.

The Greedy Strategy

1. Sort all activities by their finish time (ascending).
2. Select the first activity (it finishes earliest).
3. For each subsequent activity: if its start time ≥ the finish time of the last selected activity, select it.
4. Skip activities that overlap with the last selected one.

Why Finish Time? (Not Start Time or Duration)

• Sorting by start time fails: An activity starting at 0 but lasting until 100 blocks everything.
• Sorting by duration fails: A short activity from 4-6 might block two non-overlapping activities (1-5 and 5-9).
• Sorting by finish time works: The earliest-finishing activity leaves the maximum remaining time window for future selections.

Dry Run Example

No other selection can include more than 4 non-overlapping activities from this set.

Python Implementation

C++ Implementation

Proof of Optimality (Exchange Argument)

Claim: The greedy algorithm selects the maximum number of activities.

Proof:

1. Let G = {g₁, g₂, ..., gₖ} be the greedy solution (sorted by finish time).
2. Let O = {o₁, o₂, ..., oₘ} be an optimal solution with m ≥ k activities.
3. We show k = m.

Consider the first point of difference. Suppose g₁ ≠ o₁. Since g₁ has the earliest finish time of all activities, finish(g₁) ≤ finish(o₁). Replace o₁ with g₁ in O. This is valid because g₁ finishes no later, so it still does not conflict with o₂. Now O' = {g₁, o₂, ..., oₘ} is still a valid solution of size m.

Repeat this argument for g₂, g₃, etc. At each step, greedy's choice finishes no later than the corresponding choice in O, so the swap is always safe. After k swaps, if m > k, then O still has activities that do not conflict with gₖ. But greedy would have selected them — contradiction. Therefore m = k, and greedy is optimal. ∎

Complexity Analysis

Variations

Weighted Activity Selection

If each activity has a profit/weight, maximize total profit of selected non-overlapping activities. Greedy fails here — use DP with binary search:

Minimum Number of Rooms

Instead of maximizing activities in one room, find the minimum rooms needed to schedule all activities (equivalent to finding maximum overlap). Solution: use a sweep line or min-heap on end times.

Interval Coloring

Assign activities to minimum number of resources (rooms/machines). This extends the basic selection to a partitioning problem.

Real-World Applications

• Job scheduling: OS task scheduler, batch processing systems
• Meeting room booking: Conference room optimization in offices
• Broadcast scheduling: TV/radio program scheduling
• Bandwidth allocation: Network packet scheduling
• Exam timetabling: Non-conflicting exam slot assignment

Key Takeaways

Activity Selection is the textbook example of greedy algorithms. Sort by finish time, greedily pick non-overlapping activities. The exchange argument proves this simple strategy is optimal. The O(n log n) solution is essentially unbeatable for this problem class. When you see "maximum non-overlapping intervals," think greedy-by-finish-time immediately.