Activity Selection: A Greedy Approach

1. What is the Activity Selection Problem?

Imagine you have a single resource, like a lecture hall or a CPU, and a list of requested activities, each with a known start and finish time. Your goal is to select the maximum number of activities that can be performed without any of them overlapping.

Formally, we are given a set of $n$ activities $A=\{a_1,a_2,...,a_n\}$, where each activity $a_i$ has a start time $s_i$ and a finish time $f_i$. We want to find a maximum-size subset of mutually compatible (non-overlapping) activities. Two activities $a_i$ and $a_j$ are compatible if their intervals $[s_i,f_i)$ and $[s_j,f_j)$ do not overlap, meaning $s_i\ge f_j$ or $s_j\ge f_i$.

2. Finding the Right Greedy Choice

How do we decide which activity to pick first? A greedy algorithm needs a simple, local criterion. Let's consider a few intuitive ideas. Do they work? This exploration is crucial for building a deep understanding of why the correct strategy is not always the most obvious one.

The following video discusses a few plausible, yet incorrect, greedy strategies and shows why they fail using counter-examples. It's an excellent way to see the thought process behind designing a correct greedy algorithm.

As the video demonstrated, seemingly logical choices can fail:

• Earliest start time: Fails if the first activity is very long, blocking many other shorter activities.
• Shortest duration: Fails if a short-duration activity happens to conflict with two other activities that could have otherwise been scheduled together.
• Fewest conflicts: This also seems plausible but is more complex to compute and can also be proven to fail.

This leads us to the strategy that does work.

3. The Optimal Strategy: Earliest Finish Time

The correct and optimal greedy strategy is to always choose the activity that finishes first.

The intuition is that by picking the activity that finishes earliest, we free up the resource as soon as possible, thus maximizing the remaining time for other activities.

Let's see this strategy in action.

The algorithm is beautifully simple:

1. Sort the activities in ascending order of their finish times.
2. Select the first activity from the sorted list and add it to your solution set. Let's say its finish time is last_finish.
3. Iterate through the remaining sorted activities. For each activity, if its start time is greater than or equal to last_finish, select it, add it to the solution set, and update last_finish to the finish time of this new activity.

Complexity Analysis

As you saw in the reading, the complexity of this algorithm is dominated by the initial sorting step.

• Time Complexity: $O(n\log n)$ for sorting the activities. The subsequent iteration through the sorted list takes $O(n)$ time. Therefore, the total time complexity is $O(n\log n)$.
• Space Complexity: $O(n)$ or $O(1)$ depending on the implementation. If you can sort the array in-place and just need to store the selected activities, it's $O(k)$ where $k$ is the size of the output. If you create a new sorted copy, it's $O(n)$.

4. Proof of Correctness: A Deeper Look

You have a working algorithm. But as we discussed, the key challenge with greedy algorithms is proving they are correct. In our last lesson, you saw the "exchange argument" for the greedy choice property. Let's now formalize the complete proof for this problem, which also requires optimal substructure.

This section is for deepening your theoretical understanding, which you've expressed an interest in.

Step 1: Prove the Greedy Choice Property

We must show that the greedy choice (picking the activity with the earliest finish time) is always part of some optimal solution.

• Let $A$ be the set of activities, sorted by finish time, so $a_1$ is the activity with the earliest finish time. Our greedy choice is $a_1$.
• Let $O$ be an optimal solution. Let $o_1$ be the first activity in $O$ (also sorted by finish time).
• Case 1: $o_1=a_1$. The greedy choice is already in this optimal solution. We're done.
• Case 2: $o_1\ne a_1$. We can construct a new solution $O^{\prime }$ by replacing $o_1$ with $a_1$. Since $a_1$ has the earliest finish time of all activities, we know $f(a_1)\le f(o_1)$. Because the activities in $O$ are compatible with $o_1$, and $a_1$ finishes no later than $o_1$, they must also be compatible with $a_1$. Therefore, $O^{\prime }$ is a valid, non-overlapping schedule. It has the same number of activities as $O$, so it is also optimal.

This proves that there is always an optimal solution that begins with the greedy choice.

Step 2: Prove Optimal Substructure

We must show that an optimal solution to the problem contains optimal solutions to its subproblems.

• After making the greedy choice $a_1$, we are left with a subproblem: find the maximum number of activities from the set $S=\{a_i\in A\mid s_i\ge f(a_1)\}$. This is the set of activities that start after $a_1$ finishes.
• Let our overall solution be $O=\{a_1\}\cup O_S$, where $O_S$ is the solution to the subproblem on set $S$.
• We can prove by contradiction (a "cut-and-paste" argument) that $O_S$ must be an optimal solution for the subproblem. If there were a better solution for $S$, say $O_S^{\prime }$, with $|O_S^{\prime }|>|O_S|$, then we could form a new solution $O^{\prime }=\{a_1\}\cup O_S^{\prime }$. This solution $O^{\prime }$ would have more activities than $O$, contradicting our assumption that $O$ was optimal.

Because the problem has both the greedy choice property and optimal substructure, our greedy algorithm is guaranteed to produce a globally optimal solution.

For a more dynamic explanation of the proof, especially the exchange argument, the following video is excellent.

Conclusion

We have successfully taken the Activity Selection Problem from definition to a proven, efficient solution. This process is a model for how to approach problems that might be solvable with a greedy strategy.

Key Takeaways:

• The Activity Selection Problem aims to maximize the number of non-overlapping activities from a given set.
• The optimal greedy strategy is to sort activities by finish time and iteratively select the first available compatible activity. Other intuitive strategies, like choosing by start time or duration, are not optimal.
• The algorithm's time complexity is $O(n\log n)$, determined by the sorting step.
• The correctness of this greedy algorithm is formally proven by demonstrating it possesses both the greedy choice property (via an exchange argument) and optimal substructure.

Preview of the Next Lesson:

In the next lesson, we will explore another classic problem solved with a greedy algorithm: Huffman coding. This will show you a very different application of the greedy paradigm, used in nearly all modern data compression schemes. You'll see how making a locally optimal choice at each step—combining the two least frequent characters—leads to a globally optimal compression tree.