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

Please use the comments section below for feedback. Thanks for visiting.

2 Comments

Add a Comment

Your email address will not be published. Required fields are marked *