Weighted Activity selection problem

Problem Description

Let's consider that you have n activities with their start and finish times, the objective is to find solution set having maximum number of non-conflicting activities that can be executed in a single time frame, assuming that only one person or machine is available for execution.

It might not be possible to complete all the activities, since their timings can collapse. Two activities, say i and j, are said to be non-conflicting if si >= fj or sj >= fi where si and sj denote the starting time of activities i and j respectively, and fi and fj refer to the finishing time of the activities i and j respectively. Greedy approach can be used to find the solution since we want to maximize the count of activities that can be executed. This approach will greedily choose an activity with earliest finish time at every step, thus yielding an optimal solution.

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial	[ Brute force algorithm (1940)]
Polynomial > 3
Cubic	[ Dynamic Programming (1953)]
Quadratic	[ Dynamic Programming (1953)]
nlogn	[ Dynamic Programming (1953)]
Linear
logn