Algoritmos Greedy

Los algoritmos greedy toman la decisión que parece óptima en el momento sin considerar consecuencias futuras. La analogía: si estás haciendo cambio de $0.41 y tienes monedas de 25, 10, 5 y 1 centavo, el greedy dice: toma la moneda más grande que quepa (25¢, luego 10¢, luego 5¢, luego 1¢). Resultado óptimo con menos monedas. Greedy funciona porque con este sistema de monedas, la elección local óptima siempre lleva al óptimo global.

El desafío de los algoritmos greedy es demostrar que son correctos: no siempre la elección local óptima lleva al óptimo global. Con monedas europeas (25, 15, 1) y cambio de 30¢, greedy da 25 + 1 + 1 + 1 + 1 + 1 = 6 monedas, pero la solución óptima es 15 + 15 = 2 monedas.

Para estos casos hay que usar Programación Dinámica. Los algoritmos greedy más famosos son Huffman (compresión), Kruskal/Prim (árbol de expansión mínima) y el scheduling de tareas por plazo.

// PROBLEMA: Intervalo máximo de reuniones sin solapamiento
// Greedy: siempre toma la reunión que termina más pronto
function maxReuniones(intervalos) {
  // Ordenar por tiempo de fin
  intervalos.sort((a, b) => a[1] - b[1]);
  
  let count = 1;
  let finAnterior = intervalos[0][1];
  
  for (let i = 1; i < intervalos.length; i++) {
    if (intervalos[i][0] >= finAnterior) { // No se solapa
      count++;
      finAnterior = intervalos[i][1];
    }
  }
  return count;
}

console.log(maxReuniones([[1,3],[2,4],[3,5],[0,6]])); // 2

// PROBLEMA: Jumps - ¿puedes llegar al final?
function puedesLlegar(nums) {
  let alcance = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > alcance) return false; // No puedes llegar a esta posición
    alcance = Math.max(alcance, i + nums[i]);
  }
  return true;
}

// PROBLEMA: Mínimo de saltos para llegar al final
function minSaltos(nums) {
  let saltos = 0, alcanceActual = 0, maxAlcance = 0;
  
  for (let i = 0; i < nums.length - 1; i++) {
    maxAlcance = Math.max(maxAlcance, i + nums[i]);
    if (i === alcanceActual) { // Fin del salto actual
      saltos++;
      alcanceActual = maxAlcance;
    }
  }
  return saltos;
}

console.log(minSaltos([2,3,1,1,4])); // 2

// ALGORITMO DE HUFFMAN - compresión de datos
// Greedy: asignar códigos más cortos a caracteres más frecuentes
// La base de los formatos .zip, .jpg, .mp3

// ¿Cuándo usar Greedy vs DP?
// Greedy: cuando la elección local óptima garantiza el óptimo global
// DP: cuando hay subproblemas solapados y no hay elección greedy válida