LeetCode – Salas de reuniones II (Java)

Dada una serie de intervalos de tiempo de reunión que constan de horas de inicio y finalización [[s1,e1],[s2,e2], …]encuentre el número mínimo de salas de conferencias necesarias.

Solución Java

Cuando se toma una sala, la sala no se puede utilizar para otra reunión hasta que la reunión actual haya terminado. Tan pronto como finalice la reunión actual, la sala se puede utilizar para otra reunión. Podemos ordenar las reuniones por marcas de tiempo de inicio y asignar secuencialmente cada reunión a una sala. Cada vez que asignamos una sala para una reunión, verificamos si alguna reunión está terminada para que la sala se pueda reutilizar. Para realizar un seguimiento eficiente de la reunión final más temprana, podemos usar un montón mínimo. Siempre que una reunión anterior termina antes de que comience una nueva, reutilizamos la sala (es decir, no agregamos más espacio). De lo contrario, necesitamos una habitación adicional (es decir, agregar una habitación).

La complejidad del tiempo es O (N * log (N)).

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparing((int[] itv) -> itv[0]));
 
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int count = 0;
    for (int[] itv : intervals) {
        if (heap.isEmpty()) {
            count++;
            heap.offer(itv[1]);
        } else {
            if (itv[0] >= heap.peek()) {
                heap.poll();
            } else {
                count++;
            }
 
            heap.offer(itv[1]);
        }
    }
 
    return count;
}

Hubo una discusión en los comentarios sobre por qué una cola regular no es lo suficientemente buena. Dibujo un ejemplo a continuación para mostrar por qué es necesario ordenar según la hora de inicio y usar una cola de prioridad.