Greedy

// Template 1: sort, then match greedily. Each child needs a cookie of at least greed[i]; each cookie feeds one child.
// Walk the cookies smallest first and give each one to the least greedy child still waiting, if it is big enough.
export function findContentChildren(greed, cookies) {
  const g = [...greed].sort((a, b) => a - b);
  const c = [...cookies].sort((a, b) => a - b);
  let child = 0;
  for (let i = 0; i < c.length && child < g.length; i++) {
    if (c[i] >= g[child]) child++; // feed this child; a too-small cookie is useless to everyone left
  }
  return child;
}

// Template 2: interval scheduling. Keep the most non-overlapping intervals [start, end) by always taking
// the one that ends first among those that still fit. After k picks, no other choice of k intervals ends sooner.
export function maxNonOverlapping(intervals) {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let kept = 0;
  let lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) {   // fits after the last kept interval (touching is fine)
      kept++;
      lastEnd = end;
    }
  }
  return kept;
}

// Greedy change-making: take the largest coin that fits, again and again. Returns the coins used, or null.
// Optimal for "canonical" systems like [25, 10, 5, 1], but not for arbitrary coins.
export function greedyChange(coins, amount) {
  const desc = [...coins].sort((a, b) => b - a);
  const used = [];
  for (const coin of desc) {
    while (amount >= coin) {
      amount -= coin;
      used.push(coin);
    }
  }
  return amount === 0 ? used : null;
}

// The safe answer: dp[x] = fewest coins that make x, trying every coin as the last one. O(amount × coins).
export function minCoins(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++) {
    for (const coin of coins) if (coin <= x) dp[x] = Math.min(dp[x], dp[x - coin] + 1);
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}