Entrevista técnica de código: Mínimo de salas de reuniones

Planteamiento y casos de uso

Se te proporciona un arreglo no ordenado intervals. Cada elemento es un intervalo de tiempo entero [start, end): start está incluido y end está excluido. Por lo tanto, una reunión que termina en el tiempo t libera su sala para otra reunión que comience en t. Asume 0 <= intervals.length <= 100000 y 0 <= start < end <= 1000000000. Devuelve el número mínimo de salas requeridas para programar cada reunión.

Por ejemplo, [[0, 30], [5, 10], [15, 20]] devuelve 2; [[1, 5], [5, 8]] devuelve 1; un arreglo vacío devuelve 0. Estas son las restricciones de entrevista adoptadas por este artículo, no límites ocultos atribuidos a ninguna plataforma.

El material público proporciona varios tipos de evidencia representativa. PracHub actualizó el mismo enunciado en 2026. interviewing.io presenta el problema del mínimo de salas de reuniones como un problema de intervalos que se puede resolver con una línea de tiempo o una cola de prioridad. Un relato público de entrevista de febrero de 2026 registra preguntas de seguimiento sobre dos punteros, una cola de prioridad y un arreglo para un dominio de tiempo acotado. Las notas de algoritmos de UMass proporcionan la demostración central de partición de intervalos: cuando los intervalos se procesan por hora de inicio, el número de salas utilizadas por el algoritmo voraz (greedy) es igual a la profundidad máxima de superposición. Un único relato solo demuestra la experiencia de ese candidato, por lo que este artículo no infiere una frecuencia general de entrevista ni asigna la pregunta al banco de preguntas fijo de una empresa.

Criterios de evaluación del entrevistador

La primera señal es el modelado. Este es un problema de conteo de recursos, no de fusión de intervalos ni de selección del subconjunto compatible más grande. El número mínimo de salas equivale al número máximo de reuniones en curso en cualquier instante, a menudo denominado profundidad del conjunto de intervalos.

La segunda señal es la semántica de los extremos. Con intervalos semiabiertos, un evento de fin debe procesarse antes que un evento de inicio en el mismo instante de tiempo. Tratar start === end como una superposición asigna incorrectamente dos salas a [1, 5) y [5, 8).

La tercera señal son los invariantes y la demostración. Una vez que los inicios y los fines se ordenan por separado, los punteros ya no conservan qué fin pertenece a qué reunión. Un candidato debe explicar por qué la identidad es irrelevante cuando solo importa la ocupación concurrente: basta con saber si el siguiente evento es el inicio o el fin restante más temprano.

Finalmente, el entrevistador puede evaluar las elecciones de estructuras de datos bajo cambios de requisitos. El barrido de dos arreglos devuelve el conteo directamente. Una solicitud de asignaciones concretas de salas, la sala utilizada por cada reunión o un historial de reutilización requiere un min-heap que retenga tanto los tiempos de finalización como los identificadores de sala.

Preguntas para aclarar antes de responder

• ¿Los intervalos son [start, end) o cerrados? Este problema utiliza intervalos semiabiertos, por lo que los extremos iguales no entran en conflicto.
• ¿Son válidas las reuniones de duración cero? Este contrato requiere start < end y rechaza [t, t). Si un negocio las permite, define si consumen un recurso.
• ¿Qué debe devolver una entrada vacía? Devuelve 0, evitando cualquier error de inicialización de la primera reunión.
• ¿Devolvemos solo un conteo o también una asignación? Dos arreglos son suficientes para un conteo; la asignación debe conservar la identidad de la reunión y las salas reutilizables.
• ¿Puede la implementación mutar la entrada? La implementación a continuación copia los valores de inicio y fin y deja el arreglo del llamador intacto.
• ¿Son los tiempos enteros seguros? El límite superior establecido está dentro del rango de enteros seguros de JavaScript. Marcas de tiempo más grandes requieren un nuevo contrato de representación.
• ¿Puede la entrada ser inválida? Las entradas de entrevista suelen satisfacer el contrato. La validación en producción pertenece al límite del sistema en lugar de dentro del algoritmo central.

Estructura de respuesta de 30 segundos

“Primero confirmaría que los intervalos son semiabiertos, de modo que una sala liberada en un momento dado pueda reutilizarse de inmediato. Cuando solo se requiere el conteo mínimo, ordeno los inicios y los fines por separado y los recorro con dos punteros. Si el siguiente inicio es estrictamente anterior al fin más temprano, incremento la ocupación; de lo contrario, libero una sala primero. Mantengo el pico máximo de ocupación.

Ese pico es tanto un límite inferior como alcanzable: las reuniones simultáneas requieren salas distintas, y procesar por hora de inicio abre una nueva sala solo cuando todas las salas existentes todavía están ocupadas. La ordenación hace que el tiempo total sea O(n log n) con O(n) de espacio extra. Si el seguimiento pide una asignación concreta, usaría un min-heap que contenga los tiempos de fin y los identificadores de sala”.

Solución paso a paso

Paso 1: Calcular la ocupación máxima a partir de dos flujos de eventos ordenados

Coloca cada tiempo de inicio en starts en orden ascendente y cada tiempo de fin en ends en orden ascendente. startIndex apunta al siguiente evento de inicio no procesado, mientras que endIndex apunta al siguiente evento de fin no procesado. roomsInUse es el número de salas aún ocupadas inmediatamente después de la posición de barrido actual. Los intervalos válidos satisfacen start < end, por lo que el barrido nunca procesa un fin mientras no haya reuniones activas.

Si starts[startIndex] < ends[endIndex], el siguiente evento es un inicio: incrementa la ocupación y actualiza el pico. De lo contrario, procesa un fin primero y libera una sala. La comparación estrictamente menor que es intencional. Los extremos iguales toman la rama de liberación antes del siguiente inicio, implementando exactamente [start, end).

export function minimumMeetingRooms(
  intervals: ReadonlyArray<readonly [number, number]>,
): number {
  if (intervals.length === 0) return 0

  const starts = intervals.map(([start]) => start).sort((a, b) => a - b)
  const ends = intervals.map(([, end]) => end).sort((a, b) => a - b)

  let startIndex = 0
  let endIndex = 0
  let roomsInUse = 0
  let maximumRooms = 0

  while (startIndex < intervals.length) {
    if (starts[startIndex] < ends[endIndex]) {
      roomsInUse += 1
      maximumRooms = Math.max(maximumRooms, roomsInUse)
      startIndex += 1
    } else {
      roomsInUse -= 1
      endIndex += 1
    }
  }

  return maximumRooms
}

Rastreo de [[0, 30], [5, 10], [15, 20]]. Los inicios son 0, 5, 15; los fines son 10, 20, 30. Los inicios en 0 y 5 elevan la ocupación de 0 a 2. El fin en 10 libera una sala, reduciéndola a 1. El inicio en 15 la eleva a 2 nuevamente. El pico es 2.

Paso 2: Demostrar que el pico es el óptimo

Primero, el conteo del barrido es correcto. Representa cada [start, end) como un evento de inicio +1 y un evento de fin -1, ordena por tiempo y procesa los fines antes que los inicios en caso de empate. Después de cualquier evento, la suma acumulada es igual al número de intervalos que aún cubren la línea de tiempo inmediatamente después, que es precisamente el número de salas ocupadas. Fusionar dos arreglos ordenados con punteros recorre todos los eventos en ese orden.

A continuación, demuestra que el pico es óptimo. Sea la profundidad máxima de superposición d. En algún instante, d reuniones se ejecutan simultáneamente, por lo que cualquier planificación necesita al menos d salas; este es un límite inferior. Cuando las reuniones se procesan por tiempo de inicio, la asignación voraz abre una nueva sala solo si todas las salas existentes están ocupadas por reuniones que no han terminado. Si abre la sala k, la nueva reunión y otras k - 1 coexisten en ese instante, por lo que k <= d. Por lo tanto, existe una planificación que utiliza solo d salas. El límite superior factible es igual al límite inferior, por lo que el mínimo es d, exactamente el pico devuelto por el barrido.

Construir los arreglos cuesta O(n), las dos ordenaciones cuestan O(n log n) y el escaneo de fusión cuesta O(n). El tiempo total es O(n log n) con O(n) de espacio extra. Si los tiempos provienen de un dominio discreto pequeño y fijo, un arreglo de diferencias puede cambiar esto por un tiempo de O(n + U) y un espacio de O(U). Esa optimización no es adecuada cuando el límite de tiempo es de mil millones.

Paso 3: Elegir un heap o un arreglo de diferencias cuando cambien los requisitos

Otra solución ordena las reuniones por tiempo de inicio y mantiene el tiempo de fin de cada sala ocupada en un min-heap. Antes de procesar una reunión, extrae cada entrada con end <= start, luego inserta el nuevo tiempo de fin. El tamaño máximo del heap es la respuesta. Esto también toma un tiempo de O(n log n) y un espacio de O(n) en el peor de los casos.

Para obtener únicamente el conteo, el barrido es más corto y expone la regla de que un fin precede a un inicio empatado. El heap es valioso para extensiones: cambia cada entrada de end a { end, roomId }. Mantén un segundo min-heap de identificadores de salas disponibles, recupera los identificadores después de que terminen las reuniones y mapea cada índice de reunión original a una sala concreta. Si el requisito indica elegir la sala disponible con el número más bajo, seleccionar solo por el fin más temprano es insuficiente; las salas ocupadas y disponibles deben gestionarse por separado.

La reserva dinámica en línea es un problema diferente. Cuando las reuniones futuras llegan individualmente y pueden cancelarse, ordenar repetidamente cada intervalo puede ser demasiado costoso. La carga de trabajo de consultas puede requerir un almacén de eventos ordenados, un árbol de intervalos o un índice de calendario. La respuesta con arreglo fuera de línea de O(n log n) no debe presentarse como un diseño completo de sistema en línea.

Respuesta de muestra de alta calidad

“Resolveré esto bajo [start, end), de modo que una sala pueda reutilizarse cuando un fin sea igual a otro inicio. La verificación de conflictos por pares es una línea base válida pero cuesta O(n^2) en el peor de los casos. Con hasta 100,000 reuniones, ordenaría los eventos.

Creo arreglos ordenados de inicio y fin. Dos punteros determinan el siguiente evento: un inicio más temprano incrementa la ocupación actual y actualiza el máximo; un fin más temprano o empatado decrementa la ocupación primero. Para [[0, 30], [5, 10], [15, 20]], la ocupación cambia a través de 1, 2, 1 y 2, por lo que la respuesta es 2.

La corrección consta de dos partes. El conteo continuo del barrido es igual al número de intervalos activos, por lo que su máximo es la profundidad de superposición d. Cualquier planificación necesita al menos d salas cuando esas reuniones coexisten. Una asignación voraz por tiempo de inicio añade una sala solo mientras todas las salas existentes están ocupadas, por lo que nunca usa más de d. El algoritmo es óptimo. Toma O(n log n) de tiempo y O(n) de espacio. Si necesito el identificador de sala de cada reunión, conservaré los índices originales y asignaré salas con un heap de tiempos de finalización más un heap de identificadores disponibles”.

Errores comunes

• Error: Resolver la fusión de intervalos. Por qué falla: El número de intervalos fusionados no determina la ocupación concurrente máxima. Solución: Barre los eventos de inicio y fin y conserva el pico de conteo activo.
• Error: Procesar un inicio antes que un fin en extremos iguales. Por qué falla: Una sala que se puede reutilizar de inmediato se cuenta dos veces. Solución: Da prioridad a los eventos de fin bajo el contrato semiabierto.
• Error: Usar la ordenación predeterminada de JavaScript. Por qué falla: El orden lexicográfico coloca 10 antes que 2. Solución: Pasa (a, b) => a - b explícitamente.
• Error: Devolver el roomsInUse final. Por qué falla: La ocupación final puede ser menor que un pico anterior. Solución: Actualiza maximumRooms en cada inicio.
• Error: Comparar cada par de reuniones. Por qué falla: El tiempo en el peor de los casos se convierte en O(n^2). Solución: Ordena y fusiona los dos flujos de eventos linealmente.
• Error: Extraer solo una reunión terminada al producir asignaciones. Por qué falla: Los conjuntos activo y disponible quedan incompletos. Solución: Extrae cada sala con end <= start y gestiona los identificadores reutilizables por separado.
• Error: Dejar los límites de intervalo sin definir. Por qué falla: Las pruebas discreparán en los extremos iguales. Solución: Define intervalos semiabiertos o cerrados y la prioridad de eventos empatados antes de programar.
• Error: Agregar una atribución de empresa a partir de una etiqueta de banco de preguntas público. Por qué falla: Las etiquetas de terceros y el relato de un candidato no demuestran una autoría fija. Solución: Mantén companyName como null cuando la evidencia sea insuficiente y declara solo lo que respalda cada fuente.

Preguntas de seguimiento y respuestas

¿Por qué los dos arreglos ordenados pueden descartar la correspondencia entre reuniones?

El objetivo depende únicamente del conteo de reuniones activas en cada instante. El siguiente cambio de conteo está determinado por el inicio no procesado más temprano y el fin no procesado más temprano, independientemente de qué reunión sea propietaria de ese fin. La correspondencia se vuelve necesaria nuevamente para asignaciones o seguimientos por reunión, por lo que se debe usar un heap que contenga índices de reuniones e identificadores de sala para esos requisitos.

¿Qué cambia para intervalos cerrados [start, end]?

Un fin y un inicio en el mismo instante entran en conflicto. La comparación debe procesar el inicio primero, aumentando la ocupación cuando start <= end. La explicación más segura es definir explícitamente la prioridad en empates en lugar de cambiar mecánicamente un operador.

¿Cómo devolverías un identificador de sala para cada reunión?

Conserva los índices originales y ordena por tiempo de inicio. Mantén las salas ocupadas en un min-heap de { end, roomId }. Antes de cada reunión, mueve cada sala con end <= start a un min-heap de identificadores disponibles. Reutiliza el identificador disponible más pequeño o crea uno nuevo, luego registra assignment[originalIndex] = roomId.

¿Por qué el conteo mínimo de salas es igual a la superposición máxima?

La superposición máxima es un límite inferior inevitable porque las reuniones simultáneas no pueden compartir salas. El algoritmo voraz por tiempo de inicio abre una sala solo cuando todas las salas existentes todavía están ocupadas. Por lo tanto, cada sala que abre corresponde al mismo número de reuniones que se superponen en ese instante, por lo que nunca supera el límite inferior. La igualdad demuestra la optimalidad.

¿Qué casos extremos deben probarse?

Como mínimo, prueba un arreglo vacío, un intervalo, sin superposición, superposición completa, cadenas de extremos iguales, inicios idénticos, fines idénticos, intervalos duplicados, entrada ordenada a la inversa y datos aleatorios cerca del límite de tamaño. Un pequeño oráculo O(n^2) o de eventos discretos puede admitir pruebas diferenciales aleatorias, pero el código de verificación desechable no debe mezclarse con la implementación de producción.

¿Puede un dominio de tiempo pequeño producir una solución en tiempo lineal?

Sí. Usa un arreglo de diferencias de tamaño proporcional al dominio de tiempo U, suma uno en cada inicio, resta uno en cada fin y toma la suma de prefijos máxima. Su complejidad es de tiempo O(n + U) y espacio O(U). Vale la pena solo cuando U es pequeño y la memoria está controlada; ordenar es más seguro bajo el límite actual de mil millones.