Sesión 36: Grokking Algorithms (Capítulo 8) — Algoritmos Voraces (Greedy), Cobertura de Conjuntos e Interval Scheduling#

Navegación rápida:

← Sesión 35: Examen Global de Consolidación Semanas 1 a 4
Sesión 37: CTCI Ch8 — Backtracking: Subconjuntos y Paréntesis →
Glosario Maestro
Guía de Diagramas de Arquitectura
Tiempo estimado de estudio: 60-75 minutos.
Código fuente compilado y probado: practica-rust/dia_36.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

Iniciamos la Semana 6 explorando los paradigmas de toma de decisiones algorítmicas: comenzamos con los algoritmos voraces (Greedy), donde decisiones locales inmediatas garantizan la solución óptima o una cota de aproximación rigurosa. Consulta el Glosario Maestro y la Guía de Diagramas.

Heurística Voraz (Greedy Choice Property)#

(a) En palabras simples (intuición): Un viajero sediento en un desierto que, en cada cruce de caminos, toma siempre el sendero que tiene la pendiente más inclinada hacia abajo sin mirar el mapa completo ni pensar en si el sendero termina en un precipicio más adelante.
(b) Definición técnica paso a paso: Estrategia de optimización que en cada paso elige la mejor opción local inmediata según un criterio cuantitativo fijo, sin retroceder jamás (sin backtracking) y sin evaluar las consecuencias combinatorias globales. Produce el óptimo global si y solo si el problema satisface la propiedad de elección voraz y subestructura óptima.
(c) Cómo funciona en Rust (memoria y tipos): Opera habitualmente en un solo pase tras ordenar los datos con slice::sort_unstable_by_key, consumiendo $O(1)$ memoria auxiliar y cero llamadas recursivas.
(d) Error típico de Junior: Aplicar voracidad a problemas combinatorios que exigen reconsiderar decisiones pasadas (como la Mochila 0/1), obteniendo soluciones subóptimas.

Earliest Finish Time (EFT) en Planificación de Intervalos#

(a) En palabras simples (intuición): Si tienes un salón de fiestas y quieres alquilarlo a la mayor cantidad posible de bandas musicales en un día, aceptas primero a la banda que termine de tocar lo más temprano posible en la mañana, dejando libre la mayor parte de la tarde y la noche para otras bandas.
(b) Definición técnica paso a paso: Criterio voraz para el problema de selección de intervalos (Interval Scheduling Maximization). Ordena todos los intervalos candidatos por su tiempo de finalización ( $endᵢ$ ) en orden ascendente y selecciona iterativamente el primer intervalo compatible que comience después o exactamente al terminar el último intervalo seleccionado ( $startᵢ \geq last_end$ ).
(c) Cómo funciona en Rust (memoria y tipos): Se implementa ordenando una rebanada &mut [[i32; 2]] mediante sort_unstable_by_key(|x| x[1]), logrando tiempo $O(N log N)$ .
(d) Error típico de Junior: Ordenar los intervalos por tiempo de inicio (start time) o por duración mínima; un evento muy largo que inicie temprano bloqueará múltiples eventos cortos posteriores.

Problema de Cobertura de Conjuntos (Set Cover Problem)#

(a) En palabras simples (intuición): Quieres contratar guardias de seguridad para que vigilen 10 tiendas en un centro comercial. Cada guardia tiene permiso para vigilar solo ciertas tiendas. Quieres contratar el número mínimo de guardias posible para que ninguna tienda quede desprotegida.
(b) Definición técnica paso a paso: Problema clásico NP-Completo donde, dado un universo de elementos $U$ y una familia de subconjuntos $S$ , se busca la menor cantidad de subconjuntos cuya unión sea igual a $U$ .
(c) Cómo funciona en Rust (memoria y tipos): Se modela con HashSet<&str> para el universo pendiente y un mapa HashMap<&str, HashSet<&str>> para los subconjuntos. En cada iteración se calcula la intersección .intersection().count() para elegir el conjunto que maximiza el cubrimiento de elementos no resueltos.
(d) Error típico de Junior: Intentar fuerza bruta examinando los $2^{|S|}$ subconjuntos posibles; para 50 estaciones, $2⁵⁰ \approx 10¹⁵$ operaciones congelará la computadora.

Alcance Máximo Proyectado (Max Reach en Jump Game)#

(a) En palabras simples (intuición): Saltar entre piedras en un río. En cada piedra que pisas tienes un resorte que te permite saltar hasta cierta distancia. Miras hacia adelante y calculas cuál es la piedra más lejana a la que podrías llegar con cualquiera de los resortes que ya tienes a tu alcance.
(b) Definición técnica paso a paso: Invariante voraz que mantiene un entero escalar max_reach que representa el índice más lejano que es físicamente accesible desde cualquier punto explorado hasta el momento: $max_reach = max(max_reach, i + nums[i])$ . Si en algún momento el índice actual supera a max_reach ( $i > max_reach$ ), el destino es inalcanzable.
(c) Cómo funciona en Rust (memoria y tipos): Mantiene dos variables usize en el Stack de la CPU, resolviendo LeetCode 55 en $O(N)$ tiempo estricto y $O(1)$ memoria auxiliar.
(d) Error típico de Junior: Resolver Jump Game mediante recursión con memoización o BFS con colas, consumiendo $O(N)$ espacio innecesario y degradando el tiempo de ejecución.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

Demostración Matemática de Correctitud de EFT (Técnica del Intercambio de Argumentos)#

¿Por qué ordenar por tiempo de finalización ( $end$ ) garantiza el número máximo absoluto de intervalos compatibles? Demostración por el método del intercambio de argumentos (Exchange Argument):

Sea $G = {g₁, g₂, \dots, gₖ}$ el conjunto de intervalos seleccionados por la estrategia voraz de Earliest Finish Time (EFT), ordenados cronológicamente por hora de fin.
Supongamos que existe una solución óptima alternativa $O = {o₁, o₂, …, o_m}$ que contiene estrictamente más intervalos que la solución voraz ( $m > k$ ).
Comparemos el primer intervalo de ambas soluciones: $g₁$ y $o₁$ . - Por definición del algoritmo voraz, $g₁$ es el intervalo que termina más temprano en todo el conjunto original: $end(g₁) \leq end(o₁)$
Podemos sustituir $o₁$ por $g₁$ dentro de la solución óptima $O$ : $O' = {g₁, o₂, …, o_m}$ Como $end(g₁) \leq end(o₁)$ , $g₁$ termina antes o al mismo tiempo que $o₁$ , por lo que $g₁$ no puede colisionar con $o₂$ (ya que $o₁$ no colisionaba con $o₂$ ). Por consiguiente, la nueva solución $O'$ es válida y tiene el mismo tamaño $m$ .
Repitiendo este argumento de sustitución inductiva para los pasos $2, 3, \dots, k$ , podemos transformar la solución óptima $O$ en una solución donde los primeros $k$ intervalos son idénticos a los de $G$ .
Si $m > k$ , tendría que existir un intervalo adicional $o_{k+1}$ en la solución óptima que comience después de que termine $gₖ$ .
Pero si existiera tal intervalo, el algoritmo voraz no se habría detenido en $gₖ$ , ya que habría encontrado y seleccionado a $o_{k+1}$ (o a otro con fin aún más temprano).
¡Contradicción! Por consiguiente, $m = k$ , lo que demuestra que la solución voraz es estrictamente óptima global.

Cota de Aproximación en Cobertura de Conjuntos (Set Cover)#

Dado que Set Cover es un problema NP-completo, ningún algoritmo determinista en tiempo polinomial puede garantizar la solución mínima absoluta para todos los casos (a menos que $P = NP$ ). Sin embargo, el algoritmo voraz de Grokking Algorithms garantiza que el número de conjuntos elegidos satisface:

|S_{greedy}| ≤ H(|U|) · |S^*| ≈ (ln |U| + 1) · |S^*|

donde $|S^*|$ es el número óptimo teórico de conjuntos y $H(n)$ es el $n$ -ésimo número armónico. Para un universo de 1,000 elementos, $ln(1000) \approx 6.9$ . La solución voraz está garantizada a estar a lo sumo a un factor de $\approx 7$ veces el óptimo global, corriendo en milisegundos en lugar de millones de años.

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Diagramas de Arquitectura#

Gráfico SVG vectorial: ![Visualización del Día 36 y Memoria en Rust](../diagrams/sesiones/dia_36.svg)
Código fuente del diagrama: Fuente Mermaid

Flujo de Selección Voraz de Intervalos (LC 435)#

DIAGRAMA MERMAID

flowchart TD
    SORT["Ordenar intervalos por hora de fin creciente: end_i"] --> INIT["last_end = sorted[0].end<br/>compatibles = 1"]
    INIT --> LOOP["Para cada intervalo (start, end) desde el índice 1"]
    LOOP --> CHK{"¿start >= last_end?"}
    CHK -->|Sí (Compatible)| ADD["compatibles += 1<br/>last_end = end"]
    CHK -->|No (Conflicto)| DROP["Descartar intervalo (conflicto voraz)"]
    ADD --> NEXT["Avanzar al siguiente intervalo"]
    DROP --> NEXT
    NEXT --> COND{"¿Más intervalos?"}
    COND -->|Sí| LOOP
    COND -->|No| RES["Eliminaciones mínimas = Total - compatibles"]

Visualización Cuadro por Cuadro de Memoria en Rust (`Stack` vs `Heap`)#

Ejecución de erase_overlap_intervals(&[[1, 2], [2, 3], [3, 4], [1, 3]]):

TEXT

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| Frame erase_overlap_intervals |               | sorted: Vec<[i32; 2]>                |
|   non_overlapping: 3          |               | [ [1, 2], [2, 3], [1, 3], [3, 4] ]   |
|   last_end: 4                 |               +--------------------------------------+
|   sorted: Vec<[i32; 2]> ------+-------------->| Tras sort_unstable_by_key(|x| x[1]): |
+-------------------------------+               | 0: [1, 2] (fin: 2)                   |
                                                | 1: [2, 3] (fin: 3)                   |
                                                | 2: [1, 3] (fin: 3)                   |
                                                | 3: [3, 4] (fin: 4)                   |
                                                +--------------------------------------+

Paso 0: Toma [1, 2]. last_end = 2, compatibles = 1.
Paso 1: Evalúa [2, 3]. start(2) >= last_end(2) -> COMPATIBLE. last_end = 3, compatibles = 2.
Paso 2: Evalúa [1, 3]. start(1) < last_end(3) -> CONFLICTO. Descartar [1, 3].
Paso 3: Evalúa [3, 4]. start(3) >= last_end(3) -> COMPATIBLE. last_end = 4, compatibles = 3.

Resultado: Total (4) - compatibles (3) = 1 intervalo eliminado.

4. Las 3 Trampas Clásicas en Entrevistas#

Ordenar por Tiempo de Inicio en Interval Scheduling: - Ordenar por start en lugar de end. Si tienes un intervalo como [0, 100] seguido de diez intervalos de 1 hora [1, 2], [2, 3]..., ordenar por inicio seleccionará el de [0, 100] bloqueando los otros diez.
Confundir la Mochila Fraccionaria con la Mochila 0/1: - En una entrevista, proponer una solución Greedy ordenando por ratio $valor / peso$ para la Mochila 0/1 es un fallo grave. La voracidad solo funciona si los ítems son divisibles. Para ítems enteros e indivisibles se requiere obligatoriamente Programación Dinámica.
No Validar i > max_reach en Jump Game: - En arreglos con ceros intermedios como [3, 2, 1, 0, 4], el alcance máximo se estanca en el índice 3. Si no verificas if i > max_reach: return false, el algoritmo intentará saltar desde posiciones inalcanzables.

5. Implementación Canónica en Rust + Comparativa con Python#

Implementación Canónica en Rust (`practica-rust/dia_36.rs`)#

RUST

//! Día 36: Algoritmos Voraces (Greedy), Cobertura de Conjuntos e Interval Scheduling en Rust.
use std::collections::{HashMap, HashSet};

/// Interval Scheduling Maximization: Selección maximal de intervalos compatibles en O(N log N).
pub fn interval_scheduling(intervals: &[(i32, i32)]) -> Vec<(i32, i32)> {
    if intervals.is_empty() {
        return Vec::new();
    }

    let mut sorted = intervals.to_vec();
    sorted.sort_unstable_by_key(|&(_, end)| end);

    let mut selected = Vec::new();
    selected.push(sorted[0]);
    let mut last_end = sorted[0].1;

    for &(start, end) in sorted.iter().skip(1) {
        if start >= last_end {
            selected.push((start, end));
            last_end = end;
        }
    }

    selected
}

/// LeetCode 435: Non-overlapping Intervals en O(N log N) tiempo.
pub fn erase_overlap_intervals(intervals: &[[i32; 2]]) -> usize {
    if intervals.is_empty() {
        return 0;
    }

    let mut sorted = intervals.to_vec();
    sorted.sort_unstable_by_key(|interval| interval[1]);

    let mut non_overlapping = 1;
    let mut last_end = sorted[0][1];

    for interval in sorted.iter().skip(1) {
        let start = interval[0];
        let end = interval[1];
        if start >= last_end {
            non_overlapping += 1;
            last_end = end;
        }
    }

    intervals.len() - non_overlapping
}

/// LeetCode 55: Jump Game I en O(N) tiempo y O(1) memoria auxiliar.
pub fn can_jump(nums: &[u32]) -> bool {
    if nums.is_empty() {
        return false;
    }

    let mut max_reach = 0usize;
    let target = nums.len() - 1;

    for (i, &jump_len) in nums.iter().enumerate() {
        if i > max_reach {
            return false;
        }
        max_reach = max_reach.max(i + jump_len as usize);
        if max_reach >= target {
            return true;
        }
    }

    max_reach >= target
}

Implementación Canónica en Python (`practica/dia_36_greedy_interval_scheduling_set_cover.py`)#

PYTHON

from typing import List, Tuple

def erase_overlap_intervals(intervals: List[List[int]]) -> int:
    """LC 435: Earliest Finish Time Greedy en O(N log N)."""
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])
    count_compatible = 1
    last_end = intervals[0][1]

    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start >= last_end:
            count_compatible += 1
            last_end = end

    return len(intervals) - count_compatible

def can_jump(nums: List[int]) -> bool:
    """LC 55: Jump Game voraz rastreando max_reach en O(N) tiempo y O(1) espacio."""
    max_reach = 0
    target = len(nums) - 1

    for i, jump_len in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump_len)
        if max_reach >= target:
            return True

    return max_reach >= target

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

Pregunta 1: En Jump Game II (LeetCode 45), ¿cómo se justifica que la solución greedy equivale formalmente a una búsqueda por niveles en amplitud (BFS) sin requerir una cola FIFO?

Respuesta Técnica Detallada: En Jump Game II, el problema pide el número mínimo de saltos para alcanzar el último casillero:

Si modeláramos esto como un grafo no dirigido donde cada casillero $i$ conecta con todos los casilleros en el rango $[i+1 \dots i + nums[i]]$ , la solución clásica para caminos mínimos no ponderados es BFS por niveles.
En BFS tradicional, la frontera de nivel $k$ contiene todos los nodos alcanzables en exactamente $k$ saltos.
Al mantener dos variables escalares: curr_end (el límite derecho del nivel BFS actual) y farthest (el alcance máximo de la siguiente capa o nivel $k+1$ ):
Mientras el índice $i \leq curr_end$ , exploramos la capa actual y proyectamos farthest = max(farthest, i + nums[i]).
Cuando $i == curr_end$ , hemos agotado la capa actual: se incrementa jumps += 1 y se actualiza curr_end = farthest.

Esta técnica explora los mismos niveles que BFS pero sin asignar ningún nodo ni cola en el Heap, reduciendo la memoria de $O(N)$ a $O(1)$ estricto.

Pregunta 2: ¿Por qué en Rust usamos sort_unstable_by_key en lugar de sort_by_key para ordenar intervalos en algoritmos voraces?

Respuesta Técnica Detallada:

sort_by_key implementa un algoritmo de ordenamiento estable (Merge Sort derivado de TimSort) que preserva el orden relativo de elementos equivalentes pero requiere asignar un búfer temporal de memoria auxiliar en el Heap ( $O(N)$ memoria adicional).
sort_unstable_by_key implementa Pattern-Defeating Quicksort (pdqsort), el cual opera in-place directamente sobre el slice en la memoria RAM con $O(1)$ memoria auxiliar y factores constantes en silicio hasta 45% más rápidos.
Dado que en Interval Scheduling solo nos interesa el valor del extremo final para calcular la cota temporal, la estabilidad no añade ningún valor algorítmico, haciendo que sort_unstable_by_key sea la opción idiomática de máximo rendimiento.

Pregunta 3: ¿Qué propiedad matemática distingue a los problemas que pueden resolverse con un algoritmo Greedy de aquellos que requieren Programación Dinámica?

Respuesta Técnica Detallada: La diferencia reside en la independencia de las decisiones locales respecto a elecciones futuras:

En un problema Greedy, la elección localmente óptima en el paso actual nunca depende de la solución de subproblemas futuros ni exige reconsiderar decisiones pasadas. El espacio de búsqueda se reduce irreversiblemente a una única trayectoria lineal.
En Programación Dinámica, elegir una opción localmente atractiva en el presente puede comprometer o invalidar la viabilidad de opciones más ventajosas en el futuro (como en la Mochila 0/1 o en el problema del Cambio de Monedas). Por ello, DP debe evaluar exhaustivamente todos los subproblemas superpuestos y almacenar sus resultados para reconciliar la decisión globalmente óptima.

Pregunta 4: ¿Cómo se adapta la lógica de Interval Scheduling para resolver el problema de 'Minimum Number of Arrows to Burst Balloons' (LeetCode 452)?

Respuesta Técnica Detallada: LeetCode 452 es exactamente el problema dual de Interval Scheduling:

Cada globo es un intervalo $[x_{start}, x_{end}]$ . Disparar una flecha en una coordenada $x$ explota todos los globos que cubran ese punto.
Buscamos el conjunto independiente maximal de globos que no se solapan entre sí.
Como dos globos no solapados requieren obligatoriamente dos flechas distintas, el número mínimo de flechas necesarias es exactamente igual al número de intervalos compatibles no superpuestos que podemos agendar con Earliest Finish Time.
Ordenamos por $x_{end}$ , y cada vez que encontramos un globo que comienza después de la coordenada de la flecha anterior ( $x_{start} > last_arrow$ ), disparamos una nueva flecha en su extremo final.

Pregunta 5: ¿Por qué en el algoritmo voraz de Set Cover es fundamental restar los estados cubiertos del conjunto de pendientes en lugar de simplemente contar cuántos estados cubre la estación en total?

Respuesta Técnica Detallada: Porque de lo contrario el algoritmo caería en la trampa de la redundancia cíclica: Si una estación cubre 10 estados que ya fueron cubiertos por estaciones previamente contratadas, su contribución marginal al objetivo del problema es exactamente 0. Al calcular la intersección elements_needed.intersection(states) en cada paso, el algoritmo mide estrictamente el beneficio marginal neto que la estación aporta sobre lo que todavía falta por resolver. Esto garantiza que cada estación seleccionada maximice el avance real hacia la cobertura total.

7. Puente a LeetCode y Práctica de Código#

LeetCode 435 — Non-overlapping Intervals (Medium): - Resuelve el problema aplicando Earliest Finish Time (EFT).
LeetCode 55 — Jump Game (Medium): - Determina alcanzabilidad manteniendo el alcance máximo voraz en $O(N)$ y $O(1)$ espacio.
LeetCode 45 — Jump Game II (Medium): - Salto mínimo mediante fronteras de nivel BFS implícito.
LeetCode 452 — Minimum Number of Arrows to Burst Balloons (Medium): - Aplicación directa del principio dual de selección de intervalos.

8. Tarea en Papel para Hoy#

Toma tu cuaderno y dibuja los siguientes 6 intervalos: A: [1, 3], B: [2, 4], C: [3, 6], D: [5, 7], E: [6, 8], F: [8, 10]

Ordena los intervalos por su tiempo de finalización.
Ejecuta la traza paso a paso del algoritmo Greedy de Interval Scheduling anotando el valor de last_end en cada decisión.
Especifica los intervalos agendados finales y los descartados, verificando que el resultado sea compatible e inmejorable.

Navegación:

← Volver a Sesión 35: Examen Global de Consolidación Semanas 1 a 4
Avanzar a Sesión 37: CTCI Ch8 — Backtracking: Subconjuntos y Paréntesis →