Menu Close

Huffman Coding – Activity Selection Problem

Huffman Coding -: Greedy Algorithms 👇 👇 🙂
Link –> HUFFMAN CODING

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 TimeEnd Time
110.20 A.M11.00 A.M
210.30 A.M11.30 A.M
311.00 A.M12.00 A.M
410.00 A.M11.30 A.M
59.00 A.M11.00 A.M


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.

  • sort the activity by start time that means which activity start first we will take them first. then take first to last from sorted list and check it will intersect from previous taken activity or not. If the current activity is not intersect with the previously taken activity, we will perform the activity otherwise we will not perform. this approach will work for some cases like
Activity No.Start TimeEnd Time
111.00 A.M1.30 P.M
211.30 A.M12.00 A.M
31.30 P.M2.00 P.M
410.00 A.M11.00 A.M

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 TimeEnd Time
111.00 A.M1.30 P.M
211.30 A.M12.00 A.M
31.30 P.M2.00 P.M
410.00 A.M3.00 P.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

  • Sort the activity by time duration that means perform the shortest activity first. that can solve the previous problem . Although the problem is not completely solved. There still some cases that can fail the solution. Apply this approach on the case bellow.
Activity No.Start TimeEnd Time
16.00 A.M11.40 A.M
211.30 A.M12.00 P.M
311.40 P.M2.00 P.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

  • Sort the Activity by ending time that means the activity finishes first that come first. the algorithm is given below

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 TimeEnd Time
110.20 A.M11.00 A.M
210.30 A.M11.30 A.M
311.00 A.M12.00 A.M
410.00 A.M11.30 A.M
59.00 A.M11.00 A.M

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.

Huffman Coding -: Change-making problem 👇 👇 🙂
👉 👉 Change-making problem