Combinar intervalos en algoritmos de Java (LeetCode)

Descripción de la tarea:

Dada una matriz de intervals donde intervals[i] = [start_i, end_i] , combine todos los intervalos superpuestos y devuelva una matriz de los intervalos no superpuestos que abarcan cada intervalo de entrada .

Ejemplo 1:

 Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Ejemplo 2:

 Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Restricciones:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

Razonamiento:

Tratemos de hacer algo natural. Dibujemos intervalos del primer ejemplo. Nos ayudará a comprender la naturaleza del problema y decidir qué enfoque tomar para resolverlo.

Tenemos estos intervalos [1,3],[2,6],[8,10],[15,18]

Mirando este gráfico podemos hacer 2 observaciones esenciales.

1. Una vez que dibujamos líneas, podemos decir fácilmente cuáles se cruzan.
2. Una vez que dibujamos líneas, se ordenan.

Teniendo esto en cuenta podemos continuar con la solución.

Solución:

Lo primero que queremos hacer es ordenar todos los intervalos que tenemos. Hacemos esto para fusionarlos cuando miramos el gráfico de arriba. Es una clasificación simple, comenzamos en el punto de un intervalo y luego al final.

 Arrays.sort(intervals, (a, b) -> { if (a[1] == b[1]) { return a[0] - b[0]; } return a[1] - b[1]; });

Una vez ordenados los intervalos, podemos comenzar a fusionarlos. Mirando el gráfico anterior, podemos hacer una observación importante: los intervalos que se cruzan se superponen o comienzan en la posición final de otro intervalo. Usaremos LinkedList ya que proporciona el método getLast(). También podemos usar ArrayList y obtener el último elemento llamando a list.get(list.size() — 1). Para cada intervalo, comprobamos si tenemos una intersección con el anterior. Si tenemos una intersección, simplemente los fusionamos y los volvemos a colocar en la lista.

 LinkedList<int[]> list = new LinkedList<>(); for (int[] interval : intervals) { if (!list.isEmpty() && list.getLast()[1] >= interval[0]) { while (!list.isEmpty() && list.getLast()[1] >= interval[0]) { interval[0] = Math.min(list.getLast()[0], interval[0]); interval[1] = Math.max(list.getLast()[1], interval[1]); list.removeLast(); } } list.addLast(interval); }

Lo último que debe hacer es crear la respuesta. Lo hacemos porque no sabemos al principio cuántos elementos no se cruzan entre sí.

 int pos = 0; int[][] answer = new int[list.size()][]; for (int[] inteval : list) { answer[pos++] = inteval; }

La solución a la tarea se ve así:

 public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) -> { if (a[1] == b[1]) { return a[0] - b[0]; } return a[1] - b[1]; }); LinkedList<int[]> list = new LinkedList<>(); for (int[] interval : intervals) { if (!list.isEmpty() && list.getLast()[1] >= interval[0]) { while (!list.isEmpty() && list.getLast()[1] >= interval[0]) { interval[0] = Math.min(list.getLast()[0], interval[0]); interval[1] = Math.max(list.getLast()[1], interval[1]); list.removeLast(); } } list.addLast(interval); } int pos = 0; int[][] answer = new int[list.size()][]; for (int[] inteval : list) { answer[pos++] = inteval; } return answer; }

El código anterior se ve bien. Tiene n log n tiempo y complejidad de espacio lineal.

También publicado aquí.