Activity Selection Problem & Huffman Code

Activity Selection Problem

• First, we sort the given activity array in ascending order based on the completion time of each activity.
• After sorting, we select the first activity.
• Then, for rest of the activities, we compare the starting time of the current activity (j) with the completion time of the previous activity (i).
• If the starting time of the current activity is greater than or equal to the completion time of the previous activity, we select this activity as it is a non-overlapping activity.
• Then, we update the value of i with j and increase the count by 1.
• After completion of the loop, we return the count of total selected activities.

​

Why Use a Greedy Algorithm?

The Greedy Algorithm is based on the following intuition:

• The activity that finishes earliest has the highest chance of not conflicting with other activities.
• By selecting the activity that finishes earliest, we maximize the chances of selecting more activities in the future.

​

Time Complexity: Greedy-Activity Selector

Schedules a set of n activities in Θ(n) time, assuming that the activities were already sorted initially by their finish times.

Huffman Code

• A variable-length code can do considerably better than a fixed-length code. The idea is simple: give frequent characters short codewords and infrequent characters long codewords.
• We consider here only codes in which no codeword is also a prefix of some other codeword. Such codes are called prefix-free codes.

​

• The running time of Huffman’s algorithm depends on how the min-priority queue Q is implemented.
• Let’s assume that it’s implemented as a binary min-heap. For a set C of n characters, the BUILD-MIN-HEAP procedure discussed can initialize Q
• In line 2 in O(n) time. The for loop in lines 3–10 executes exactly n − 1 times, and since each heap operation runs in O(lg n) time, the loop contributes O(n lg n) to the running time. Thus, the total running time of HUFFMAN on a set of n characters is O(n lg n).