Greedy algorithm activity selection problem
Activity selection problem greedy algorithm
Assume that you are an administrator who is in charge of a conference room equipped with some expensive telepresence system. Different employees or groups of employees need to have access to the conference room but they can not use the telepresence system at the same time. Every day employees who want to use the system inform you in advance which time slot they will be using the equipment. Your goal is to serve the maximum number of employees at a given day. Your input is a list of employees along with the time period during which they want to use the room. The output should be a list (maximum possible size) of employees with none overlapping time slots. Develop an algorithm to automate this task.
Activity selection problem using greedy method
This is a well known problem called Activity Selection. We need to select the maximum number of compatible activities. In our case an activity is using the conference room and compatibility refers to the time periods being none overlapping. A greedy approach can be used to select a list of employees with maximum size. Selecting the shortest time slot first will not give us an optimum solution. Here is a counter example: if we have only the following time slots 12PM-3PM, 2PM-4PM, 3PM-6PM then selecting the shortest time slot yields 2PM-3PM while the other two time slots can not be added to the solution because they overlap with the selected time slot. On the other hand if we just take 12PM-3PM and 3PM-6PM since they are not overlapping and exclude the shortest one because it overlaps with those two then we get two time slots as compared to only one in the first case. In other words selecting the shortest time slot will not guarantee an optimum solution.
Another greedy approach that does not work is to select the time slot which overlaps with the least number of other time slots. Here is a counter example: 5 employees 10AM-12PM, one employee 12PM-2PM, one employee 2PM-4PM, one employee 1PM-3PM and 5 employees 4PM -6PM. As you can see selecting the time slot which overlaps with the least number of other intervals gives us 1PM-3PM which means we need to take out 12PM-2PM and 2PM-4PM because they overlap with 1PM-3PM. After that we serve one employee only 10AM-12PM and one employee only 4PM-6PM because we can not serve 5 employees during the same time period. The total number of employees we have served this way is 3. It is very easy to tell that 3 is not the maximum that we can serve simply because we can serve up to 4 employees as follows 10AM-12PM, 12PM-2PM, 2PM-4PM and 4PM-6PM.
The only greedy approach that works for solving the activity selection problem is to sort the list of activities by finish time in an increasing order then serve the employee whose time slot finishes first while removing other intervals that overlap with the selected activity.
Activity selection problem greedy algorithm code
Here is an example activity selection problem greedy algorithm program in c sharp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
using System; using System.Collections.Generic; namespace ActivitySelection { class ActivitySelector { //Number of time slots private int n = 11; //Array of time slots private int[,] A; //Constructor public ActivitySelector() { //Sample time slot array. Note that we are assuming //the array is already sorted by finish time in an //increasing order. It is a two dimensional array //where A[i, 0] is the start time of time slot (i) //and A[i, 1] is the finish time of time slot (i) A = new int[11, 2] { {10, 12}, {10, 12}, {10, 12}, {11, 13}, {12, 14}, {13, 15}, {14, 16}, {16, 18}, {16, 18}, {16, 18}, {17, 19} }; } public void Select() { //First time slot is by default part of the //solution Console.WriteLine(A[0, 0] + "-" + A[0, 1]); //j index points to the time slot that was //added to the optimum solution int j = 0; //Loop in the list of activities until //reaching a time slot that does not //overlap with slot (j) for (int i = 1; i < n; i++) { //If the (i) activity has a start time //greater than or equal to the finish //time of the (j) activity then add the //(i) activity to the solution if (A[i, 0] >= A[j, 1]) { Console.WriteLine(A[i, 0] + "-" + A[i, 1]); //Update (j) j = i; } } } } //Main program class Program { //Main static void Main(string[] args) { //Create object ActivitySelector selector = new ActivitySelector(); //Demo algorithm selector.Select(); } } } |
Please use the comments section below for feedback. Thanks for visiting.
hi
I am also working on this problem, but I think maybe there is some mistake in your counter example for greedy selection based on least overlaps. The first activity selected based on least overlaps should be either 12-2 or 2-4, which only overlaps with one other activity (1-3). So selection based on least overlaps gives an optimal solution for this example. btw. I found a counter example that works at
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/actSelectionGreedy.htm
Thanks for the feedback. I will update the post whenever I get time 🙂