| FazBrowse Wikipedia Viewer | Main Page | | |
| Viewing: https://en.wikipedia.org/wiki/Activity_selection_problem |
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. The activity selection problem is also known as the Interval scheduling maximization problem (ISMP), which is a special type of the more general Interval Scheduling problem.
A classic application of this problem is in scheduling a room for multiple competing events, each having its own time requirements (start and end time), and many more arise within the framework of operations research.
A.Lines 10,11: If the start time A[i]) is greater or equal to the finish time A[i] is compatible to the selected activities in the set A[i].
Let k≠1, i.e., this optimal solution does not start with the greedy choice. We will show that |A|=|B|, B is also optimal.
Once the greedy choice is made, the problem reduces to finding an optimal solution for the subproblem. If A is an optimal solution to the original problem S containing the greedy choice, then k. We can recursively find solutions for these two sets because of optimal sub-structure. As we don't know (i,j), we can find the optimal solution if we had known the solution for j in (i,j) but instead just Weighted-Activity-Selection(S):// S = list of activities sortSbyfinishtime opt[0]=0// opt[j] represents optimal solution (sum of weights of selected activities) for S[1,2..,j] fori=1ton: t=binarysearchtofindactivitywithfinishtime<=starttimefori // if there are more than one such activities, choose the one with last finish time opt[i]=MAX(opt[i-1],opt[t]+w(i)) returnopt[n]
| View original on Wikipedia | Back | FazBrowse Home |