Algorithms Greedy algorithms suggest change

Activity Selection Problem

The Problem

You have a set of things to do (activities). Each activity has a start time and a end time. You aren’t allowed to perform more than one activity at a time. Your task is to find a way to perform the maximum number of activities.

For example, suppose you have a selection of classes to choose from.

Activity No.| start time| end time| —— | —— | —— |

|1| 10.20 A.M | 11.00AM | |2| 10.30 A.M | 11.30AM | |3| 11.00 A.M | 12.00AM | |4| 10.00 A.M | 11.30AM | |5| 9.00 A.M | 11.00AM |

Remember, you can’t take two classes at the same time. That means you can’t take class 1 and 2 because they share a common time 10.30 A.M to 11.00 A.M. However, you can take class 1 and 3 because they don’t share a common time. So your task is to take maximum number of classes as possible without any overlap. How can you do that?

Analysis

Lets think for the solution by greedy approach.First of all we randomly chose some approach and check that will work or not.

Activity No.| start time| end time| —— | —— | —— |

|1| 11.00 A.M | 1.30P.M | |2| 11.30 A.M | 12.00P.M | |3| 1.30 P.M | 2.00P.M | |4| 10.00 A.M | 11.00AM |

the sorting order will be 4–>1–>2–>3 .The activity 4–> 1–> 3 will be performed and the activity 2 will be skipped. the maximum 3 activity will be performed. It works for this type of cases. but it will fail for some cases. Lets apply this approach for the case

Activity No.| start time| end time| —— | —— | —— |

|1| 11.00 A.M | 1.30P.M | |2| 11.30 A.M | 12.00P.M | |3| 1.30 P.M | 2.00P.M | |4| 10.00 A.M | 3.00P.M |

The sort order will be 4–>1–>2–>3 and only activity 4 will be performed but the answer can be activity 1–>3 or 2–>3 will be performed. So our approach will not work for the above case. Let’s try another approach

Activity No.| start time| end time| —— | —— | —— |

|1| 6.00 A.M | 11.40A.M | |2| 11.30 A.M | 12.00P.M | |3| 11.40 P.M | 2.00P.M |

if we sort the activity by time duration the sort order will be 2–> 3 —>1 . and if we perform activity No. 2 first then no other activity can be performed. But the answer will be perform activity 1 then perform 3 . So we can perform maximum 2 activity.So this can not be a solution of this problem. We should try a different approach.


The solution

  1. Sort the activities by its ending times.
  2. If the activity to be performed do not share a common time with the activities that previously performed, perform the activity.

Lets analyse the first example

Activity No.| start time| end time| —— | —— | —— |

|1| 10.20 A.M | 11.00AM | |2| 10.30 A.M | 11.30AM | |3| 11.00 A.M | 12.00AM | |4| 10.00 A.M | 11.30AM | |5| 9.00 A.M | 11.00AM |

sort the activity by its ending times , So sort order will be 1–>5–>2–>4–>3.. the answer is 1–>3 these two activities will be performed. ans that’s the answer. here is the sudo code.

  1. sort: activities
  2. perform first activity from the sorted list of activities.
  3. Set : Current_activity := first activity
  4. set: end_time := end_time of Current activity
  5. go to next activity if exist, if not exist terminate .
  6. if start_time of current activity <= end_time : perform the activity and go to 4
  7. else: got to 5.

see here for coding help http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents