Estrategia de Solución

El núcleo voraz de este problema reside en: ordenar los globos por su borde derecho y hacer que una sola flecha atraviese la mayor cantidad posible de globos superpuestos.

1. Ordenamiento: Clasifica todos los globos en orden ascendente según su borde derecho (¡clave! Prioriza el manejo de globos con bordes derechos más pequeños para maximizar la posibilidad de superposición posterior).
2. Disparo de Flechas:
   • Inicializa la posición de la primera flecha en el borde derecho del primer globo.
   • Itera sobre los globos subsiguientes: si el borde izquierdo del globo actual es mayor que la posición de la flecha, significa que no se puede alcanzar con la flecha actual, por lo que se necesita una nueva flecha, y la posición de la flecha se actualiza al borde derecho del globo actual; de lo contrario, la flecha actual puede alcanzar este globo y no se necesita ninguna operación.
3. El número total de flechas es la respuesta final.

Código Completo en Java

import java.util.Arrays;
import java.util.Comparator;

class Solution {
   public int findMinArrowShots(int[][] points) {
       if (points == null || points.length == 0) {
           return 0;
       }
       
       // Paso 1: Ordenar por el borde derecho de los globos en orden ascendente
       Arrays.sort(points, Comparator.comparingLong(a -> a[1]));
       
       // Paso 2: Inicializar el número de flechas y la posición de la primera flecha
       int arrowCount = 1;
       long currentArrowPos = points[0][1]; // Usar long para evitar desbordamiento
       
       // Paso 3: Iterar sobre los globos, determinando si se necesita una nueva flecha
       for (int i = 1; i < points.length; i++) {
           // Si el borde izquierdo del globo actual es mayor que la posición de la flecha, se necesita una nueva flecha
           if (points[i][0] > currentArrowPos) {
               arrowCount++;
               currentArrowPos = points[i][1];
           }
           // De lo contrario, la flecha actual puede alcanzar este globo, no se necesita operación
       }
       
       return arrowCount;
   }
}
     

Análisis del Código

1. Manejo de Bordes: Si el arreglo de globos está vacío, retorna 0.
2. Clave del Ordenamiento: Ordenar por el borde derecho en orden ascendente es el núcleo de la estrategia voraz — disparar en la posición del borde derecho más pequeño puede cubrir la mayor cantidad de globos superpuestos posteriores; ten en cuenta el uso de Long para almacenar la posición de la flecha y evitar desbordamientos de int (el rango de coordenadas en el problema puede ser muy grande).
3. Iteración para Disparar: El número inicial de flechas es 1 (se necesita al menos una flecha), y la posición de la flecha es el borde derecho del primer globo; itera sobre los globos subsiguientes, y si el borde izquierdo de un globo excede la posición de la flecha, significa que no puede ser cubierto, se agrega una flecha y se actualiza la posición de la flecha al borde derecho del globo actual.

Estrategia de Solución

El núcleo voraz de este problema es: ordenar los intervalos por su borde derecho, priorizar la preservación de intervalos con bordes derechos más pequeños para maximizar el espacio restante (esencialmente, "mínimo de eliminación = total - máximo de preservación").

1. Ordenamiento: Clasifica los intervalos en orden ascendente según su borde derecho.
2. Contar el número máximo de intervalos no superpuestos que se pueden preservar:
   • Inicializa el número de preservados en 1, y el borde derecho del intervalo previamente preservado en el borde derecho del primer intervalo.
   • Itera sobre los intervalos subsiguientes: si el borde izquierdo del intervalo actual es mayor o igual al borde derecho del intervalo previamente preservado, significa que no se superponen, incrementa el contador de preservados en 1 y actualiza el borde derecho del intervalo previamente preservado; de lo contrario, omite este intervalo (este intervalo necesita ser eliminado).
3. Calcular el número de eliminaciones: Número total de intervalos - número máximo de preservados.

Código Completo en Java

import java.util.Arrays;
import java.util.Comparator;

class Solution {
   public int eraseOverlapIntervals(int[][] intervals) {
       if (intervals == null || intervals.length == 0) {
           return 0;
       }
       
       // Paso 1: Ordenar por el borde derecho de los intervalos en orden ascendente
       Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
       
       // Paso 2: Contar el número máximo de intervalos no superpuestos que se pueden preservar
       int preservedCount = 1; // Al menos preservar 1 intervalo
       int lastRightBoundary = intervals[0][1]; // Límite derecho del intervalo previamente preservado
       
       for (int i = 1; i < intervals.length; i++) {
           // Si el borde izquierdo del intervalo actual es >= al borde derecho del último preservado, no se superponen, preservar
           if (intervals[i][0] >= lastRightBoundary) {
               preservedCount++;
               lastRightBoundary = intervals[i][1];
           }
       }
       
       // Paso 3: Número de eliminaciones necesarias = Total - Preservados
       return intervals.length - preservedCount;
   }
}
     

Análisis del Código

1. Manejo de Bordes: Retorna 0 si el arreglo de intervalos está vacío.
2. Lógica de Ordenamiento: Ordenar por el borde derecho en orden ascendente es la clave voraz — preservar el intervalo con el borde derecho más pequeño deja más espacio para los intervalos posteriores, permitiendo así preservar más intervalos no superpuestos.
3. Contar Intervalos Preservados: El número inicial de preservados es 1 (el primer intervalo), y se itera sobre los intervalos subsiguientes; siempre que no se superpongan con el intervalo previamente preservado, se preservan y se actualiza el borde derecho.
4. Calcular Número de Eliminaciones: El número total de intervalos menos el número máximo de preservados es el número mínimo de intervalos que necesitan ser eliminados.

Estrategia de Solución

Aunque este problema parece ser de cadenas, en realidad es una variante de la división de intervalos superpuestos. El núcleo voraz es: registrar primero la última aparición de cada letra, y luego encontrar el borde derecho máximo del intervalo actual.

1. Preprocesamiento: Itera sobre la cadena, registra el índice de la última aparición de cada letra (equivalente al "borde derecho del intervalo" de cada letra).
2. Dividir Intervalos:
   • Inicializa el borde izquierdo del intervalo actual start = 0, y el borde derecho máximo del intervalo actual end = 0.
   • Itera sobre la cadena:
     • Actualiza end al máximo entre la "posición de la última aparición de la letra actual" y el end actual (extendiendo el borde derecho del intervalo actual).
     • Si el índice iterado es igual a end, significa que todas las letras dentro del intervalo actual aparecen solo dentro de este intervalo, registra la longitud del intervalo (end - start + 1), y actualiza start = end + 1 para comenzar el siguiente intervalo.
3. Devuelve una lista de las longitudes de todos los intervalos.

Código Completo en Java

import java.util.ArrayList;
import java.util.List;

class Solution {
   public List<integer> partitionLabels(String s) {
       List<integer> partitionLengths = new ArrayList<>();
       // Paso 1: Registrar el índice de la última aparición de cada letra (mapeo por código ASCII)
       int[] lastOccurrenceIndex = new int[26];
       for (int i = 0; i < s.length(); i++) {
           lastOccurrenceIndex[s.charAt(i) - 'a'] = i;
       }
       
       // Paso 2: Dividir los intervalos
       int intervalStart = 0; // Límite izquierdo del intervalo actual
       int intervalEnd = 0;   // Límite derecho máximo del intervalo actual
       
       for (int i = 0; i < s.length(); i++) {
           // Actualizar el límite derecho máximo del intervalo actual
           intervalEnd = Math.max(intervalEnd, lastOccurrenceIndex[s.charAt(i) - 'a']);
           // Si se llega al límite derecho del intervalo, registrar la longitud
           if (i == intervalEnd) {
               partitionLengths.add(intervalEnd - intervalStart + 1);
               intervalStart = intervalEnd + 1; // Reiniciar el límite izquierdo, comenzar el siguiente intervalo
           }
       }
       
       return partitionLengths;
   }
}
     </integer></integer>

Análisis del Código

1. Preprocesamiento de Últimos Índices: Se utiliza un arreglo de tamaño 26 (correspondiente a las 26 letras minúsculas) para registrar el índice de la última aparición de cada letra, con una complejidad de tiempo de O(n).
2. Núcleo de la División de Intervalos:
   • intervalStart marca la posición de inicio del intervalo actual, y intervalEnd marca el borde derecho máximo del intervalo actual (asegurando que las últimas apariciones de todas las letras dentro del intervalo estén dentro de intervalEnd).
   • Cuando se llega a i == intervalEnd, significa que todas las letras dentro del intervalo actual no aparecerán en posiciones posteriores, en este punto se divide el intervalo y se registra su longitud.
3. Devolución del Resultado: Todas las longitudes de los intervalos se almacenan en una lista y se devuelven. La complejidad de tiempo general es O(n) y la complejidad de espacio es O(1) (solo se utiliza un arreglo de tamaño fijo).

Resumen

1. Mínimo de Flechas para Explotar Globos: El núcleo voraz es "ordenar por el borde derecho, una flecha atraviesa la mayor cantidad de globos superpuestos", la clave es disparar en la posición del borde derecho más pequeño.
2. Intervalos sin Superposición: El núcleo voraz es "ordenar por el borde derecho, preservar la mayor cantidad de intervalos no superpuestos", el número mínimo de eliminaciones = total - máximo de preservados.
3. Partición de Cadenas por Letras: El núcleo voraz es "registrar primero la última posición de las letras, luego encontrar el borde derecho máximo del intervalo actual", esencialmente es una división de intervalos superpuestos en versión de cadena.