Activity Selection

Activity Selection Problem

Given a list of activities where each activity has a start time and an end time, determine the maximum number of non-overlapping activities that can be performed. You must choose activities such that no two selected activities overlap in time.

Input

• A list of activities, where each activity is represented by an object or tuple with two values: start and end.

Output

• An integer representing the maximum number of activities that can be performed without overlap.

Example

For example, given the following list of activities:

activities = [
    { start: 1, end: 4 },
    { start: 3, end: 5 },
    { start: 0, end: 6 },
    { start: 5, end: 7 },
    { start: 8, end: 9 },
    { start: 5, end: 9 }
]

The maximum number of non-overlapping activities you can select is 4. One optimal selection is: activities with intervals [1,4], [5,7], [8,9] (and for example, adding an extra if available). Note that the exact choice might vary based on sorting, but the maximum count remains.

Hint

A common greedy strategy is to first sort the activities by their end times. Then, iterate through them and select an activity if its start time is not less than the finish time of the last selected activity.

Happy coding on this fine day of March 3rd!