Peter is an energetic guy, and usually has many things to do in a given day. However, with the amount of things he wants to do, he is usually unable to do them all in a single day. What he usually does after waking up is write up a list of activities that he has to do, along with their time span. Then, looking at that list, he devises a plan for the day, trying to accommodate as many activities as possible.

Being an energetic guy, he usually rushes through this process and finds himself doing fewer activities than possible throughout the day. Can you help him maximize the amount of activities he can do in a day, given his schedule? An example of a schedule for Peter is given in the following table:

This is known as the activity selection problem. The problem is to schedule several competing activities that require exclusive use of a common resource (which is Peter, in this case), with the goal of selecting a maximum size set of activities that are mutually compatible.

In other words, we are trying to find the biggest set of activities that Peter can perform in a day. Each activity (a_i) has a start time (s_i) and a finish time (f_i). Two activities, a_i and a_j, are considered compatible if the intervals (s_i, f_i) and (s_j, f_j) do not overlap, for example, s_i ≥ f_j or s_j ≥ f_i.

Looking at Peter's schedule, and converting the start and finish times to minutes since the start of a day, we can arrive at the following table. To convert the times to minutes since the start of the day, we multiply the hours by 60 and add the minutes. For example, activity 1 runs from 10:00 to 12:00. 10:00 is 600 (10*60 + 0) minutes since the start of the day, and 12:00 is 720 (12*60 + 0) minutes since the start of the day:

For this example, the subset {a₁, a₃, a₅, a₆} consists of mutually compatible activities, as their times don't overlap. It is not a maximum subset (that is, we can find a set with a larger number of activities), since the subset {a₃, a₄, a₅, a₆, a₇, a₁₁} is larger (note that the order of the activities is a₄, a₇, a₁₁, a₃, a₅ and a₆). In fact, it is a larger subset of mutually compatible activities. It is not the only one: another possible larger subset is {a₁, a₇, a₁₁, a₃, a₅, a₆}.

How should we approach this problem to find the maximum size set of activities that are mutually compatible? It turns out we should do the greedy choice. What this means is that, at each step of the algorithm, from the set of activities that we can still perform, we should choose one greedily.

The greedy choice may not be immediate, but you can intuitively think that we should select activities that leave Peter available for as many other activities as possible.

We can have two approaches to resolve this problem, and they are as follows:

• Always choose the activity with the earliest starting time; however, we can have the activity with the earliest starting time finishing after all the other activities.
• Choose the activity that consumes the least amount of time; however, we can have a small activity overlapping two or more non-overlapping activities (for example, activities [1, 4), [3, 5) and [4, 8)).

Hence, both of these approaches don't work.

From the set of activities that we are able to choose, we must choose the first one to finish, as that is the activity that would leave Peter available for as many of the activities that follow it as possible. If we sort activities by finish time, we can then always select the first activity we find that is compatible with the last activity selected for Peter.