You need to login before you can make any post submission.
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.
Standard Greedy Algorithm Problems:
Given n activities with their start and finish times.
Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.
Example-1: Consider the following 3 activities sorted by finish time.
start[] = {10, 12, 20}
finish[] = {20, 25, 30}
Output: (10, 20) (20, 30)
Example-2: Consider the following 6 activities sorted by finish time.
start[] = {3 , 0 , 5 , 8 , 5, 1}
finish[] = {4 , 6 , 9 , 9 , 7, 2}
Output: (1, 2) (3, 4) (5, 7) (8, 9)
def activity_selection(start, finish):
activities = []
n = len(start)
for i in range(n):
activities.append((start[i], finish[i]))
# Sort the activities by finish time in increasing order and if finish times same then start time in decreasing order
activities.sort(key=lambda k: (k[1], -k[0]))
print("Selected Activities:")
prev_finish = 0
for current_start, current_finish in activities:
if(current_start >= prev_finish):
print("({}, {})".format(current_start, current_finish))
prev_finish = current_finish
print("Example-1:")
start = [10, 12, 20]
finish = [20, 25, 30]
activity_selection(start, finish)
print("\nExample-2:")
start = [3 , 0 , 5 , 8 , 5, 1]
finish = [4 , 6 , 9 , 9 , 7, 2]
activity_selection(start, finish)
# Time : O(n log n) if input activities not sorted.
# : O(n) if input activities are sorted.
# Auxilliary Space: O(n) :-> Creating a new array but can be done in O(1)
Output:
Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits.
Example:
Input:
arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
def min_number_of_platforms_required(arrivals, departures):
n = len(arrivals)
arrivals.sort()
departures.sort()
i =0; j=0; count = 0; platforms =0
while(i<n and j<n):
if(arrivals[i] < departures[j]):
count += 1
i += 1
else:
if(count > platforms):
platforms = count
count -= 1
j += 1
print("Minimum Number of Platforms required = {}".format(platforms))
print("Example-1:")
arrivals = [9.00, 9.40, 9.50, 11.00, 15.00, 18.00]
departures = [9.10, 12.00, 11.20, 11.30, 19.00, 20.00]
min_number_of_platforms_required(arrivals, departures)
# Time Complexity : O(n log n) if arrivals & departures are not sorted.
# : O(n) if arrivals & departures are sorted.
# Auxilliary Space: O(1)
Output:
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.
Example:
character
Frequency
a ————————> 5
b ————————> 9
c ————————> 12
d ————————> 13
e ————————> 16
f ————————> 45
Step-1: Build a min heap that contains 6 nodes where each node represents root of a tree with single node.
Step-2: Extract two minimum frequency nodes from min heap. Add a new internal node with frequency 5 + 9 = 14.
Now min heap contains 5 nodes where 4 nodes are roots of trees with single element each, and one heap node is root of tree with 3 elements.
character
Frequency
c ————————> 12
d ————————> 13
Internal Node ———> 14
e ————————> 16
f ————————> 45
Step 3: Extract two minimum frequency nodes from heap. Add a new internal node with frequency 12 + 13 = 25.
character
Frequency
Internal Node ———> 14
e ————————> 16
Internal Node ———> 25
f ————————> 45
Step 4: Extract two minimum frequency nodes. Add a new internal node with frequency 14 + 16 = 30.
Now min heap contains 3 nodes.
character
Frequency
Internal Node ———>25
Internal Node ———> 30
f ————————> 45
Step 5: Extract two minimum frequency nodes. Add a new internal node with frequency 25 + 30 = 55.
Now min heap contains 2 nodes.
character
Frequency
f ———————> 45
Internal Node ——>55
Step 6: Extract two minimum frequency nodes. Add a new internal node with frequency 45 + 55 = 100
Now min heap contains only one node.
character
Frequency
Internal Node ——>100
Since the heap contains only one node, the algorithm stops here.
The Codes are as follows:
character
Codes
f —————> 0
c —————> 100
d —————> 101
a —————> 1100
b —————> 1101
e —————> 111
import heapq
class HeapNode:
def __init__(self, char, frequency):
self.char = char
self.frequency = frequency
self.left = None
self.right = None
def __lt__(self, other):
return self.frequency < other.frequency
def build_huffman_tree(chars, frequencies):
# Create a leaf node for each unique character and build a min heap of all leaf nodes
n = len(chars)
custom_heap = []
for i in range(n):
heap_node = HeapNode(chars[i], frequencies[i])
heapq.heappush(custom_heap, heap_node)
# Extract two nodes with the minimum frequency from the min heap and start merging
while(len(custom_heap) > 1):
node_left = heapq.heappop(custom_heap)
node_right = heapq.heappop(custom_heap)
merged_node = HeapNode(None, node_left.frequency+node_right.frequency)
merged_node.left = node_left
merged_node.right = node_right
heapq.heappush(custom_heap, merged_node)
# Root Node of the Heap
root_node = heapq.heappop(custom_heap)
return root_node
def print_huffman_code(node, code):
if(node.left == None and node.right == None):
print("{}: {}".format(node.char, code))
return
print_huffman_code(node.left, code+"0")
print_huffman_code(node.right, code+"1")
def generate_huffman_code(chars, frequencies):
root_node = build_huffman_tree(chars, frequencies)
print_huffman_code(root_node, "")
print("Huffman Codes for characters:")
chars = ['a', 'b', 'c', 'd', 'e', 'f']
frequencies = [5, 9, 12, 13, 16, 45]
generate_huffman_code(chars, frequencies)
# Time Complexity : O(nlogn) where n is the number of unique characters.
# To extract Min using heappop() takes O(logn) and as there are n nodes, it is called 2*(n – 1) times.
# Auxilliary Space : O(n) :-> Storing n nodes in heap
Output:
Time : O(nlogn) where n is the number of unique characters.
: To extract Min using heappop() takes O(logn) and as there are n nodes, it is called 2*(n – 1) times.
Auxilliary Space : O(n) : Storing n nodes in heap