Back to Study Material Data Structures and Algorithms

Activity Selection

The activity selection problem asks: given n activities, each with a start time and finish time, select the maximum number of non-overlapping activities th...

Activity Selection

Understanding the Activity Selection Problem

The activity selection problem asks: given n activities, each with a start time and finish time, select the maximum number of non-overlapping activities that a single resource can perform. Two activities i and j are compatible if one finishes before the other starts, meaning finish[i] <= start[j] or finish[j] <= start[i].

The greedy insight is simple but powerful: always select the activity that finishes earliest among the remaining compatible activities. By finishing early, you leave the most room for future activities. This greedy choice is provably optimal using an exchange argument — any solution that skips the earliest-finishing compatible activity can swap it back in without reducing the count.

Algorithm outline: sort all activities by finish time in ascending order. Initialize the result set with the first activity. Iterate through the remaining activities; if the current activity starts at or after the finish time of the last selected activity, add it to the result. Time complexity is O(n log n) for sorting plus O(n) for the scan, giving O(n log n) overall. Space complexity is O(n) to store the result.

A worked example: activities with (start, finish) pairs — (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16). After sorting by finish: (1,4), (3,5), (0,6), (5,7), ... Greedy picks (1,4), then (5,7), then (8,11), then (12,16) — four activities.

Interview tip: Clarify whether activities are half-open intervals (finish <= start allowed) or open intervals (finish < start required). This subtle boundary condition often changes which activities are compatible and can affect your count by one.

Proof of Optimality via Exchange Argument

To prove the greedy activity selection algorithm is optimal, we use a classic exchange argument. Let G be the greedy solution and O be any optimal solution, both represented as sorted sequences of activities. We will show |G| >= |O|.

Compare G and O position by position. At the first index where they differ, let g_k be the greedy choice and o_k be the optimal choice. By the greedy rule, g_k has a finish time no later than o_k (because greedy always picks the earliest finisher). Replace o_k with g_k in O; since finish(g_k) <= finish(o_k), the replacement cannot cause any subsequent activity in O to become incompatible — if an activity was compatible with o_k, it is compatible with g_k. Call this modified solution O'. We have |O'| = |O| and O' agrees with G one more position than before.

Repeating this swap process transforms O into G without ever reducing the number of activities. Therefore |G| >= |O|. Since O was arbitrary and optimal, G is also optimal. This argument is tight and elegant — it directly shows structural equivalence between greedy and optimal.

Understanding the exchange argument deeply lets you adapt it to variants. For example, if activities have weights (profits) and you want maximum profit, the exchange argument breaks, which is why weighted activity selection requires dynamic programming instead.

Interview tip: If an interviewer asks you to explain why greedy works here but not for the weighted version, walk through exactly where the exchange argument breaks: replacing a high-profit activity with a low-profit early-finisher reduces total profit, so the transform is no longer neutral.

Variants and Real-World Applications

Activity selection generalizes to several important variants encountered in practice and interviews. The weighted activity selection problem assigns a value to each activity and asks for the subset with maximum total value among non-overlapping activities. This variant requires dynamic programming: sort by finish time, define dp[i] as the maximum value using activities from 1 to i, and use binary search to find the latest compatible activity for each i. Time complexity becomes O(n log n).

Another variant allows k machines instead of one. You want to schedule as many activities as possible across k parallel resources. A greedy solution uses a min-heap of size k tracking when each machine next becomes free. For each activity sorted by start time, assign it to the machine that becomes free earliest (if it is free in time), or skip it. This runs in O(n log k) time.

Real-world applications include CPU scheduling (choose the process that finishes soonest to maximize throughput), meeting room booking systems (determine whether a room is free for a requested time slot), and broadcast scheduling (decide which programs to air to fill a time slot optimally). The interval scheduling structure appears in compiler register allocation, where registers are viewed as time slots and variable live ranges as activities.

A practical implementation detail: when finish times are equal, break ties by start time (latest start first) to reduce overlap ambiguity, though any tie-breaking rule preserves optimality.

Interview tip: When the problem gives you activities on a timeline and asks for maximum count, immediately recognize the activity selection pattern. Saying "I will sort by finish time and greedily extend my schedule" in the first thirty seconds of the problem discussion signals strong pattern recognition to interviewers.