Leetcode/Guide/Greedy

Contents

The Greedy Algorithm is a powerful problem-solving technique that builds up a solution piece by piece, always choosing the best local option at each step — hoping that these choices lead to the globally optimal solution.

It doesn’t always guarantee the absolute best answer, but for many well-defined problems, it works perfectly.

---

🧠 Core Idea

1. Make a choice that looks best at the moment (the “greedy choice”).
2. Never reconsider previous decisions.
3. Continue until the entire problem is solved or no choices remain.

Greedy algorithms are often used when:

• A local optimum leads to a global optimum.
• You can safely choose the best option available at each step.
• The problem satisfies the Greedy Choice Property and Optimal Substructure.

---

Example 1 — Coin Change (Minimum Coins)

Given a set of coin denominations, find the minimum number of coins that make up a target amount.

⚠️ Works perfectly when coin denominations are canonical (like U.S. coins).

function minCoinsGreedy(denominations, amount) {
  denominations.sort((a, b) => b - a); // sort descending
  const result = [];
  let remainingAmount = amount;

  for (const coin of denominations) {
    while (remainingAmount >= coin) {
      remainingAmount -= coin;
      result.push(coin);
    }
  }

  return result;
}

// Demo
console.log(minCoinsGreedy([25, 10, 5, 1], 63)); 
// Output: [25, 25, 10, 1, 1, 1] (6 coins)

✅ Why this works:
Choosing the largest coin first minimizes the remaining amount most quickly — and for standard denominations, it gives the optimal result.

---

Example 2 — Activity Selection (Maximize Non-Overlapping Intervals)

Given a list of activities with start and end times, find the maximum number of activities you can do without overlapping.

function selectMaxActivities(activities) {
  // Sort by earliest finishing time
  activities.sort((a, b) => a.end - b.end);

  const selected = [];
  let lastEndTime = -Infinity;

  for (const activity of activities) {
    if (activity.start >= lastEndTime) {
      selected.push(activity);
      lastEndTime = activity.end;
    }
  }

  return selected;
}

// Demo
const activities = [
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 4, end: 6 },
  { start: 6, end: 7 },
  { start: 5, end: 8 },
  { start: 8, end: 9 }
];

console.log(selectMaxActivities(activities));
// Output: activities ending at [3, 6, 7, 9]

✅ Why this works:
By always picking the activity that finishes earliest, we leave as much room as possible for the next one — the greedy choice ensures the maximum count.

---

Example 3 — Fractional Knapsack

Given items with value and weight, and a bag capacity, maximize total value.
Unlike the 0/1 knapsack, here we can take fractions of an item.

function fractionalKnapsack(items, capacity) {
  // Sort 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) {
      totalValue += item.value;
      remainingCapacity -= item.weight;
    } else {
      // Take a fraction
      const fraction = remainingCapacity / item.weight;
      totalValue += item.value * fraction;
      remainingCapacity = 0;
    }
  }

  return totalValue;
}

// Demo
const items = [
  { value: 60, weight: 10 },
  { value: 100, weight: 20 },
  { value: 120, weight: 30 }
];

console.log(fractionalKnapsack(items, 50)); 
// Output: 240 (full 20kg + 30kg fraction)

✅ Why this works:
Choosing the item with the highest value density first always leads to the optimal total value for the fractional version.

---

Example 4 — Huffman Encoding (Minimize Total Cost)

A greedy approach to minimize average code length based on character frequency.

class MinHeap {
  constructor() { this.data = []; }
  insert(value) {
    this.data.push(value);
    this.data.sort((a, b) => a - b);
  }
  extractMin() { return this.data.shift(); }
}

function huffmanEncoding(frequencies) {
  const heap = new MinHeap();
  frequencies.forEach(f => heap.insert(f));

  while (heap.data.length > 1) {
    const first = heap.extractMin();
    const second = heap.extractMin();
    heap.insert(first + second);
  }

  return heap.extractMin();
}

// Demo
console.log(huffmanEncoding([5, 9, 12, 13, 16, 45])); 
// Output: 224 (total cost of tree)

✅ Why this works:
By repeatedly combining the two smallest frequencies, we minimize the total weighted path length — a classic greedy property.

---

Example 5 — Interval Merging (Greedy + Sorting)

Merge overlapping intervals by always expanding the current merged range.

function mergeIntervals(intervals) {
  intervals.sort((a, b) => a.start - b.start);
  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    const current = intervals[i];

    if (current.start <= last.end) {
      last.end = Math.max(last.end, current.end);
    } else {
      merged.push(current);
    }
  }

  return merged;
}

// Demo
const inputIntervals = [
  { start: 1, end: 3 },
  { start: 2, end: 6 },
  { start: 8, end: 10 },
  { start: 15, end: 18 }
];

console.log(mergeIntervals(inputIntervals));
// Output: [{start:1,end:6},{start:8,end:10},{start:15,end:18}]

✅ Why this works:
By sorting and merging greedily when intervals overlap, we ensure minimal merged ranges.

---

🧩 Summary Table

---

🚀 Key Takeaways

• Greedy algorithms optimize locally at each step.
• They’re simple, fast (O(n log n) typical), and elegant when applicable.
• Always check that your problem meets:
  • Greedy Choice Property
  • Optimal Substructure
• Works best for:
  • Scheduling
  • Resource allocation
  • Optimization problems

Greedy ≈ “Pick what looks best now — trust it works out later.”