Greedy Algorithms

Make the locally optimal choice at each step. Master Activity Selection, Huffman Coding, and Fractional Knapsack for problem optimization and complexity.

1. The Hook: Just Take It

Most algorithms (DP, Backtracking) look at future consequences. Greedy algorithms live in the moment. They take the best immediate payoff, hoping it leads to the global optimum.

• Pro: Blazing fast (O(N log N) or O(N)).
• Con: Only works for specific problems (Matroids).

---

2. The Pattern: Activity Selection

Problem: You have N meetings with [start, end]. Pick the maximum number of non-overlapping meetings.

Greedy Choice: Always pick the meeting that ends earliest.

• Why? Finishing early leaves the most time for future meetings.
• Invariant: The optimal solution S_opt agrees with our greedy choice at step 1.

Algorithm:

1. Sort by end time.
2. Pick first.
3. Skip all overlapping.
4. Repeat.

---

3. Huffman Coding (Compression)

Problem: Compress string “aaabbc”. Greedy Choice: Combine the two least frequent characters into a small tree.

1. Frequency Map: a:3, b:2, c:1.
2. Priority Queue: [c:1, b:2, a:3].
3. Pop c and b. Combine to cb:3. Insert back.
4. Pop cb and a. Combine to root:6.

Result: Frequent chars get short codes. Rare chars get long codes.

---

4. Implementation: Activity Selection

Java

Go

public int maxMeetings(int[][] meetings) {
  // Sort by end time
  Arrays.sort(meetings, (a, b) -> Integer.compare(a[1], b[1]));

  int count = 0;
  int lastEnd = -1;

  for (int[] m : meetings) {
    if (m[0] > lastEnd) {
      count++;
      lastEnd = m[1];
    }
  }
  return count;
}

import "sort"

func maxMeetings(meetings [][]int) int {
  // Sort by end time
  sort.Slice(meetings, func(i, j int) bool {
    return meetings[i][1] < meetings[j][1]
  })

  count := 0
  lastEnd := -1

  for _, m := range meetings {
    if m[0] > lastEnd {
      count++
      lastEnd = m[1]
    }
  }
  return count
}

---

5. Intution: Fractional Knapsack

You are a thief with a bag of capacity W. You see piles of gold dust, silver dust, and flour. What do you take?

• Greedy: Take the item with highest Value Per Pound.
• Fractional: You can take 0.5 lbs of gold. (Greedy Works!)
• 0/1 Knapsack: You must take the whole bar. (Greedy Fails! Need DP).

---