Excel VBA – Activity Selection Algorithm

Wikipedia says that the activity selection problem is a combinatorial optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time (si) and finish time (fi). The problem is to select the maximum number of activities that can be performed by a single person or machine, assuming that a person can only work on a single activity at a time.

 

download

It is a great example of a greedy algorithm – we simply take the activity that ends first and then we take the next one possible, which also finishes last. The above picture, translated to excel input looks like this:

sortingActivity

What we need to solve the algorithm is one class for Activity, where we can have StartTime and EndTime and one sorting implementation. First we sort by EndTime, then we take the first one in the collection and we start looping. If the n-th sorted element has an available starting time and the smallest ending time, then it’s ok. It works automatically and provides the best solution. In our case it is like this:

This is the code in the module:

This is the code in the clsAction:

Here is the GitHub code.

Tagged with: , , ,