Activity selection problem
Encyclopedia
The activity selection problem is a mathematical 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.
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
.
to find a solution will always result in an optimal solution. A pseudocode
sketch of the algorithm and a proof of the optimality of its result are included below.
Suppose, A is a subset of S is an optimal solution and let activities in A be ordered by finish time. Suppose, the first activity in A is k.
If k = 1, then A begins with greedy choice and we are done (or to be very precise, there is nothing to prove here).
If k not=1, we want to show that there is another solution B that begins with greedy choice, activity 1.
Let B = A - {k} U {1}. Because f[1] =< f[k], the activities in B are disjoint and since B has same number of activities as A, i.e., |A| = |B|, B is also optimal.
Once the greedy choice is made, the problem reduces to finding an optimal solution for the problem. If A is an optimal solution to the original problem S, then A` = A - {1} is an optimal solution to the activity-selection problem S` = {i in S: s[i] >= f[1]}.
Why? If we could find a solution B` to S` with more activities then A`, adding 1 to B` would yield a solution B to S with more activities than A, there by contradicting the optimality.
Task (project management)
In project management a task is an activity that needs to be accomplished within a defined period of time. An assignment is a task under the responsibility of an assignee which should have a start and end date defined. One or more assignments on a task puts the task under execution. Completion of...
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.
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
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
.
Formal definition
Assume there exist n activities with each of them being represented by a start time si and finish time fi. Two activities i and j are said to be non-conflicting if si ≥ fj or sj ≥ fi. The activity selection problem consists in finding the maximal solution set (S) of non-conflicting activities, or more precisely there must exist no solution set S' such that |S'| > |S| in the case that multiple maximal solutions have equal sizes.Optimal Solution
The activity selection problem is notable in that using a greedy algorithmGreedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
to find a solution will always result in an optimal solution. A pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
sketch of the algorithm and a proof of the optimality of its result are included below.
Algorithm
- Sort the set of activities by finishing time (f[i])
- S = {1}
- f = f[1]
- for i=1 to n
- if s[i] ≥ f
- S = S U i
- f = f[i]
- if s[i] ≥ f
- endfor
Proof of optimality
Let S = {1, 2, . . . , n} be the set of activities ordered by finish time. Thus activity 1 has the earliest finish time.Suppose, A is a subset of S is an optimal solution and let activities in A be ordered by finish time. Suppose, the first activity in A is k.
If k = 1, then A begins with greedy choice and we are done (or to be very precise, there is nothing to prove here).
If k not=1, we want to show that there is another solution B that begins with greedy choice, activity 1.
Let B = A - {k} U {1}. Because f[1] =< f[k], the activities in B are disjoint and since B has same number of activities as A, i.e., |A| = |B|, B is also optimal.
Once the greedy choice is made, the problem reduces to finding an optimal solution for the problem. If A is an optimal solution to the original problem S, then A` = A - {1} is an optimal solution to the activity-selection problem S` = {i in S: s[i] >= f[1]}.
Why? If we could find a solution B` to S` with more activities then A`, adding 1 to B` would yield a solution B to S with more activities than A, there by contradicting the optimality.