Let’s follow the next classic Greedy problem. You have a list of activities with start and finish times. The problem is to schedule some activities so the number of them is maximum, but there are no overlaps (a person can only do one task at the moment).

Here, the approach is similar to the previous trivial problem with items and the box. Now, the items are time intervals of activities, and the size of the box is between min(start) and max(end), but the order of activities affects, too.

items contains tuples (start_i, end_i) for each event.

Algorithm:

1. Sort all activities by their ending time.

2. Choose the first activity and add it to the list

3. For each next activity, choose the closest next one, such that finish[curr] <= start[next], i. e. you can pick the next activity only if the current is over.

Why does this algorithm work?

Since our approach is to pick the activity with the least finish time (let's say finish[curr]), imagine that we pick some other activity, for example, finish[curr+k], k>0, and this solution is optimal.

Thus, finish[curr] <= finish[curr+k], and the number of activities of both solutions are the same, so they are both optimal. Anyway, since both are optimal, let’s choose the less one.

By picking curr activity we can achieve more ‘empty’ space for the next activities, that’s why this is more beneficial.

The formal explanation you can find here.

Example 1

items=[(1, 3), (4, 7), (2, 3), (4,10), (10,11), (7,9)]

res=[(1, 3), (4, 7), (7,9), (10,11)]

Note that (2, 3) could be instead of (1,3), but our algorithm returns the (1,3) and it does not affect the total number of activities.

Example 2

items=[(0, 3), (9,10), (2, 7), (6, 9), (4,10), (2,9)].

res=[(0,3), (6,9), (9,10)]