Greedy Algorithms

Greedy Algorithms

Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum. They're faster than DP but don't always give the optimal solution.

Activity Selection Problem

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

Coin Change (Greedy - not always optimal)

function coinChangeGreedy(coins, amount) {
  coins.sort((a, b) => b - a); // Descending
  const result = [];
  
  for (const coin of coins) {
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }
  return amount === 0 ? result : null;
}

// Works for standard coin systems (1, 5, 10, 25)
// May not work for arbitrary coin systems!

Fractional Knapsack

function fractionalKnapsack(items, capacity) {
  // Sort by value/weight ratio

  

    
Learn More
    

      
        
GeeksforGeeks: Greedy
        
Learn about Greedy Algorithms and their applications.
      
      
        
LeetCode: Greedy
        
Solve problems that can be optimized using greedy approaches.
      
    
  

  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  
  let totalValue = 0;
  
  for (const item of items) {
    if (capacity >= item.weight) {
      totalValue += item.value;
      capacity -= item.weight;
    } else {
      totalValue += item.value * (capacity / item.weight);
      break;
    }
  }
  return totalValue;
}