11 — Greedy Algorithms

What is Greedy?

Make the locally optimal choice at each step, hoping it leads to a globally optimal solution. No backtracking.

Greedy works when:
  ✅ Greedy choice property — local optimal → global optimal
  ✅ Optimal substructure — optimal solution contains optimal sub-solutions

Greedy fails when:
  ❌ Local best ≠ global best (need DP instead)

---

Activity Selection

Select maximum non-overlapping activities.

function activitySelection(activities: [number, number][]): number {
  // Sort by end time
  activities.sort((a, b) => a[1] - b[1]);
  
  let count = 1;
  let lastEnd = activities[0][1];
  
  for (let i = 1; i < activities.length; i++) {
    if (activities[i][0] >= lastEnd) {
      count++;
      lastEnd = activities[i][1];
    }
  }
  return count;
}

---

Interval Scheduling

Minimum meeting rooms

function minMeetingRooms(intervals: [number, number][]): number {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
  
  let rooms = 0, maxRooms = 0, e = 0;
  for (let s = 0; s < starts.length; s++) {
    if (starts[s] < ends[e]) {
      rooms++;
    } else {
      e++;
    }
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}

Merge Overlapping Intervals

function merge(intervals: [number, number][]): [number, number][] {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged: [number, number][] = [intervals[0]];
  
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      merged.push(intervals[i]);
    }
  }
  return merged;
}

---

Fractional Knapsack

Take fractions of items (unlike 0/1 knapsack which needs DP).

function fractionalKnapsack(items: [number, number][], W: number): number {
  // Sort by value/weight ratio (descending)
  items.sort((a, b) => (b[0] / b[1]) - (a[0] / a[1])); // [value, weight]
  
  let totalValue = 0;
  for (const [value, weight] of items) {
    if (W >= weight) {
      totalValue += value;
      W -= weight;
    } else {
      totalValue += (value / weight) * W;
      break;
    }
  }
  return totalValue;
}

---

Huffman Coding

Optimal prefix-free encoding — frequent characters get shorter codes.

function huffman(freq: Map<string, number>): Map<string, string> {
  // Min-heap of [frequency, node]
  const heap: [number, { char?: string; left?: any; right?: any }][] = [];
  
  for (const [char, f] of freq) {
    heap.push([f, { char }]);
  }
  
  while (heap.length > 1) {
    heap.sort((a, b) => a[0] - b[0]);
    const [f1, left] = heap.shift()!;
    const [f2, right] = heap.shift()!;
    heap.push([f1 + f2, { left, right }]);
  }
  
  // Generate codes by traversing tree
  const codes = new Map<string, string>();
  function traverse(node: any, code: string) {
    if (node.char) { codes.set(node.char, code || '0'); return; }
    if (node.left) traverse(node.left, code + '0');
    if (node.right) traverse(node.right, code + '1');
  }
  traverse(heap[0][1], '');
  return codes;
}

---

Jump Game

// Can you reach the last index?
function canJump(nums: number[]): boolean {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}

// Minimum jumps to reach end
function jump(nums: number[]): number {
  let jumps = 0, curEnd = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === curEnd) {
      jumps++;
      curEnd = farthest;
    }
  }
  return jumps;
}

---

Greedy vs DP

---

Key Takeaways

• Greedy = sort + scan pattern in most problems
• Activity selection: sort by end time, pick non-overlapping
• Intervals: sort by start (merge) or end (selection), use two-pointer
• Fractional knapsack: sort by value/weight ratio — greedy works
• Always prove greedy choice property before using greedy over DP