Problem

Input:$s_{1},…,s_{n}$ start times and $t_{1},…,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

- Sort activities according to their end times.
- At each step, pick the earliest end time, and remove any activities that overlap with it.
- 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 $OPT$ solution that agrees with the first $k$ activities in $G$. Then, there exists an $OPT_{′}$ solution such that it’s

- feasible (meets our constraints, meaning no activities overlap)
- $∣OPT∣≤∣OPT_{′}∣$
- $OPT_{′}$ contains activities $t_{1},t_{2},…,t_{k}$ as well as $t_{k+1}$

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

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

### Case 1

Trivial, $OPT_{′}=OPT$ since it already contains activity $k+1$.

### Case 2

Since $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_{∗}$ be the next activity that $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_{∗}$ cannot start past $k+1$.

We can construct $OPT_{′}=OPT−{t_{∗}}∪{t_{k+1}}$. Now, $OPT_{′}$ is still feasible.

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

Therefore, we can keep exchanging optimal solutions until $G=OPT_{′}$.

## Runtime

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