Problem
Input: start times and 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 ) 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 solution that agrees with the first activities in . Then, there exists an solution such that it’s
- feasible (meets our constraints, meaning no activities overlap)
- contains activities as well as
We want to get one more activity closer to our greedy solution .
Now, has the exact same first activities selected (remember, we sorted by end times). contains activity . We have two cases: either contains or doesn’t contain .
Case 1
Trivial, since it already contains activity .
Case 2
Since chose a different interval than , we know that the next interval it chooses has to end past the end time of . Let be the next activity that picks.
- Otherwise, it would be the same as , which we know it didn’t pick. (There could be multiple activities with the same end time as .)
- Also, the start time has to be in the interval that contains . Otherwise, we could’ve just added , which we didn’t, so cannot start past .
We can construct . Now, is still feasible.
- This is because the end time of has to be after . Then, the activity after has to start later than the activity after . This means that replacing with causes no overlaps, which makes this valid.
- We exchanged one activity with another. The number of elements remain the same.
- now contains activity , which is one step closer to .
Therefore, we can keep exchanging optimal solutions until .
Runtime
Runtime is dominated by sorting, which is by the Lower bound for comparison-based sorting algorithms. Iterating through the activities only takes .