Problema de Referencia

Considermeos el problema de determinar cuántos árboles permanecen después de remover varios tramos de una calle. Existen múltiples enfoques, pero las técnicas de diferencias proporcionan una solución elegante y óptima.

Método 1: Enfoque Directo (No Recomendado)

static void resolverDirecto() {
    Scanner scanner = new Scanner(System.in);
    int longitud = scanner.nextInt();
    int segmentos = scanner.nextInt();
    int[] arboles = new int[longitud + 1];
    
    for (int i = 0; i <= longitud; i++) {
        arboles[i] = 1;
    }
    
    for (int i = 0; i < segmentos; i++) {
        int inicio = scanner.nextInt();
        int fin = scanner.nextInt();
        
        for (int j = inicio; j <= fin; j++) {
            arboles[j] = 0;
        }
    }
    
    int conteo = 0;
    for (int valor : arboles) {
        if (valor == 1) conteo++;
    }
    
    System.out.println(conteo);
}

Método 2: Técnica de Diferencias (Recomendado)

static void resolverConDiferencias() {
    Scanner scanner = new Scanner(System.in);
    int longitud = scanner.nextInt();
    int segmentos = scanner.nextInt();
    int[] diferencial = new int[longitud + 2];
    
    for (int i = 0; i < segmentos; i++) {
        int inicio = scanner.nextInt();
        int fin = scanner.nextInt();
        
        diferencial[inicio]--;
        diferencial[fin + 1]++;
    }
    
    int acumulado = 0;
    int totalArboles = 0;
    
    for (int i = 0; i <= longitud; i++) {
        acumulado += diferencial[i];
        if (acumulado == 0) {
            totalArboles++;
        }
    }
    
    System.out.println(totalArboles);
}

La técnica de diferencias funciona registrando solo los puntos de cambio en lugar de modificar cada elemento del intervalo. Al calcular la suma acumulada, podemos determinar qué posiciones fueron afectadas por al menos un intervalo.

Método 3: Fusión de Intervalos

static void resolverConFusion() {
    Scanner scanner = new Scanner(System.in);
    int longitud = scanner.nextInt();
    int segmentos = scanner.nextInt();
    List<Intervalo> intervalos = new ArrayList<>();
    
    for (int i = 0; i < segmentos; i++) {
        int inicio = scanner.nextInt();
        int fin = scanner.nextInt();
        intervalos.add(new Intervalo(inicio, fin));
    }
    
    intervalos.sort(Comparator.comparingInt(Intervalo::getInicio));
    
    List<Intervalo> fusionados = new ArrayList<>();
    for (Intervalo actual : intervalos) {
        if (fusionados.isEmpty()) {
            fusionados.add(actual);
        } else {
            Intervalo ultimo = fusionados.get(fusionados.size() - 1);
            
            if (actual.getInicio() <= ultimo.getFin()) {
                ultimo.setFin(Math.max(ultimo.getFin(), actual.getFin()));
            } else {
                fusionados.add(actual);
            }
        }
    }
    
    int totalEliminado = fusionados.stream()
        .mapToInt(it -> it.getFin() - it.getInicio() + 1)
        .sum();
    
    System.out.println((longitud + 1) - totalEliminado);
}

static class Intervalo {
    int inicio, fin;
    
    Intervalo(int inicio, int fin) {
        this.inicio = inicio;
        this.fin = fin;
    }
    
    int getInicio() { return inicio; }
    int getFin() { return fin; }
    void setFin(int fin) { this.fin = fin; }
}

Este método combina intervalos superpuestos antes de calcular, lo que permite una solución matemática directa especialmente útil cuando el espacio es muy grende.

Aplicaciones Adicionales

Las técnicas de diferencias y sumas acumuladas son aplicables en:

• Actualizacioens de rango en arreglos
• Detección de superposiciones temporales
• Procesamiento de señales
• Análisis de cobertura geográfica