Greedy Algorithms

A Greedy Algorithm is a paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate, obvious benefit.

It makes the locally optimal choice at each stage with the hope that these local choices will lead to a globally optimal solution.

Real-Life Analogy

Think of Making Change for a $100 Bill. If a cashier needs to give you $86 in change, they don't use dynamic programming. They use a Greedy Algorithm:

1. What is the largest bill I can give without going over $86? A $50. (Remaining: $36)
2. What is the largest bill for $36? A $20. (Remaining: $16)
3. Next? A $10. (Remaining: $6)
4. Next? A $5. (Remaining: $1)
5. Next? A $1. (Done).

By always grabbing the absolute largest bill possible (the locally optimal choice), the cashier successfully returns the minimum total number of bills.

[!WARNING] Greedy algorithms do NOT always work! If the available currency was $1, $15, and $25, and you needed to make $30 in change:

• Greedy approach: Grabs a $25. Then needs five $1s. (Total: 6 bills).
• Optimal approach: Grabs two $15s. (Total: 2 bills).

You can only use a Greedy algorithm if the problem exhibits the "Greedy Choice Property" (local optimums guarantee global optimums).

Classic Problem: Fractional Knapsack

You are a thief carrying a backpack that holds W pounds. You break into a vault with items of varying weights and values. You can take fractions of items (e.g., 50% of the gold dust). How do you maximize value?

The Greedy Choice: Always take the item with the highest Value-to-Weight Ratio.

interface Item {
  weight: number;
  value: number;
}

function fractionalKnapsack(capacity: number, items: Item[]): number {
  // Sort items by Value-to-Weight ratio descending
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  
  let totalValue = 0;
  let remainingCapacity = capacity;
  
  for (const item of items) {
    if (remainingCapacity === 0) break;
    
    if (item.weight <= remainingCapacity) {
      // Take the whole item
      totalValue += item.value;
      remainingCapacity -= item.weight;
    } else {
      // Take a fraction of the item to perfectly fill the bag
      const fraction = remainingCapacity / item.weight;
      totalValue += item.value * fraction;
      remainingCapacity = 0;
    }
  }
  
  return totalValue;
}

Classic Problem: Activity Selection

You are given $N$ meetings with start and end times. You have one conference room. Find the maximum number of meetings you can schedule.

The Greedy Choice: Always pick the meeting that ends the earliest. This leaves the maximum possible free time for the remaining meetings.

function maxMeetings(start: number[], end: number[]): number {
  // Pair up the start and end times
  const meetings = start.map((s, i) => ({ start: s, end: end[i] }));
  
  // Sort by END time ascending
  meetings.sort((a, b) => a.end - b.end);
  
  let count = 0;
  let lastEndTime = -1;
  
  for (const meet of meetings) {
    // If this meeting starts after the previous one finished, we can attend!
    if (meet.start >= lastEndTime) {
      count++;
      lastEndTime = meet.end;
    }
  }
  
  return count;
}

Time Complexity

Most Greedy algorithms revolve around sorting the input data first. Therefore, the time complexity is almost always dominated by the sort: $O(N \log N)$. The greedy pass itself is usually just $O(N)$.