Unweighted activity selection

Problem

Input: $s_1,\dots ,s_n$ start times and $t_1,\dots ,t_n$ end times.

Output: max number of activities such that activities do not overlap.

Similar to Weighted activity selection from 5M except we don’t have a reward for picking an activity, which makes deciding which activity to pick more difficult.

Potential top level questions

How do we decide which activity to pick next? What’s the criteria we look for?

• Pick one with the earliest finish time? (this is the correct one)
• Pick latest finish time first?
• Smallest (in terms of $t_i-s_i$) activity first?
• Fewest overlap?

Algorithm

1. Sort activities according to their end times.
2. At each step, pick the earliest end time, and remove any activities that overlap with it.
3. Keep recursing on new set of activities until we have none left.

Proof of correctness

We will use an Exchange argument and induction: assume by IH, there exists an $\text{OPT}$ solution that agrees with the first $k$ activities in $G$. Then, there exists an ${\text{OPT}}^{\prime }$ solution such that it’s

1. feasible (meets our constraints, meaning no activities overlap)
2. $|\text{OPT}|\le |{\text{OPT}}^{\prime }|$
3. ${\text{OPT}}^{\prime }$ contains activities $t_1,t_2,\dots ,t_k$ as well as $t_{k+1}$

We want to get one more activity closer to our greedy solution $G$.

Now, $\text{OPT}$ has the exact same first $k$ activities selected (remember, we sorted by end times). $G$ contains activity $k+1$. We have two cases: $\text{OPT}$ either contains or doesn’t contain $k+1$.

Case 1

Trivial, ${\text{OPT}}^{\prime }=\text{OPT}$ since it already contains activity $k+1$.

Case 2

Since $\text{OPT}$ chose a different interval than $k+1$, we know that the next interval it chooses has to end past the end time of $k+1$. Let $t_{\ast }$ be the next activity that $\text{OPT}$ picks.

• Otherwise, it would be the same as $k+1$, which we know it didn’t pick. (There could be multiple activities with the same end time as $k+1$.)
• Also, the start time has to be in the interval that contains $k+1$. Otherwise, we could’ve just added $k+1$, which we didn’t, so $t_{\ast }$ cannot start past $k+1$.

We can construct ${\text{OPT}}^{\prime }=\text{OPT}-\{t_{\ast }\}\cup \{t_{k+1}\}$. Now, ${\text{OPT}}^{\prime }$ is still feasible.

1. This is because the end time of $t_{\ast }$ has to be after $t_{k+1}$. Then, the activity after $t_{\ast }$ has to start later than the activity after $t_{k+1}$. This means that replacing $t_{\ast }$ with $t_{k+1}$ causes no overlaps, which makes this valid.
2. We exchanged one activity with another. The number of elements remain the same.
3. ${\text{OPT}}^{\prime }$ now contains activity $k+1$, which is one step closer to $G$.

Therefore, we can keep exchanging optimal solutions until $G={\text{OPT}}^{\prime }$.

Runtime

Runtime is dominated by sorting, which is $O(n\log n)$ by the Lower bound for comparison-based sorting algorithms. Iterating through the activities only takes $O(n)$.