$1$ Greedy Activity Selection $(15$ pt$.)$

Activity Selection is a classic algorithms problem. It works as follows: you are given a schedule with n activities, each of which has a start and finish time. You must select a subset of the greatest possible size, subject to the constraint that none of the activities within overlap. Below is an example schedule.

Time

Two valid solutions to this schedule are $\{$a$1,$ a$2,$ a$6,$ a$7\},$ and $\{$a$1,$ a$3,$ a$6,$ a$7\}.$ Two invalid solutions are $\{$a$1,$ a$2,$ a$6\}($we only include three activities when we could include four$)$ and $\{$a$1,$ a$2,$ a$6,$ a$8\}($two of the activities overlap$).$

Consider the following greedy algorithm for activity selection. The idea is that at each step, we greedily add a valid activity with the fewest conflicts with other valid activities. $($An activity is valid if it doesn$$t conflict with an already selected activity$).$

The algorithm $($breaking ties arbitrarily$)$ could choose a$1,$ then a$6,$ then a$7,$ then a$2.$

Is this algorithm correct?

$[$We are expecting: Either a short English explanation for why this algorithm always succeeds, or a counterexample to show that it doesn$$t$.]$