Lesson 8.1: Activity Selection
The Activity Selection problem involves choosing the maximum number of non-overlapping activities from a set of activities that each have a start and finish time. This is a classic example of the greedy approach where at each step, we pick the activity that finishes the earliest.
📌 Key Points
- Sort activities by finish time.
- Select the first activity, then continue picking activities that start after the last selected one ends.
- Used in scheduling tasks, CPU job scheduling, etc.
- Greedy choice ensures optimal solution in this case.
- Doesn't work for all problems—greedy needs problem-specific justification.
- Efficient: O(n log n) due to sorting + linear scan.
- Can be visualized with timelines for understanding.
🧪 Examples
# Activity selection example
activities = [(1, 3), (2, 5), (4, 7), (6, 9), (8, 10)]
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
print(selected)
# Output: [(1, 3), (4, 7), (8, 10)]
Lesson 8.2: Huffman Coding
Huffman Coding is a compression algorithm used to reduce the size of data. It assigns variable-length codes to input characters, with shorter codes assigned to more frequent characters. This is widely used in file compression formats such as ZIP and JPEG.
📌 Key Points
- Uses a binary tree structure to build prefix codes.
- More frequent characters get shorter codes.
- No code is a prefix of another — avoids ambiguity.
- Build a min-heap of characters by frequency.
- Merge two lowest frequency nodes until one tree remains.
- Final tree gives prefix-free encoding.
- Greedy strategy ensures minimum total encoded size.
🧪 Examples
# Huffman coding skeleton using heapq
import heapq
from collections import Counter, namedtuple
Node = namedtuple("Node", ["freq", "char", "left", "right"])
def huffman(freq_map):
heap = [[freq, Node(freq, char, None, None)] for char, freq in freq_map.items()]
heapq.heapify(heap)
while len(heap) > 1:
freq1, left = heapq.heappop(heap)
freq2, right = heapq.heappop(heap)
merged = Node(freq1 + freq2, None, left, right)
heapq.heappush(heap, [freq1 + freq2, merged])
return heap[0][1]
freq_map = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
huffman(freq_map)
# Output is a Huffman tree, traversal gives codes