Explicar una fusión de intervalos
Linden Rooms necesita fusionar las reservas que se solapan para una sala. La entrada contiene intervalos semiabiertos en minutos enteros [start, end), y los intervalos adyacentes deben seguir separados. Explica un algoritmo y recorre en voz alta sus casos límite.
Rúbrica y preparaciónRespuesta de nivel mid: qué cubre · 3 lecciones para prepararte
Intermedio estándar
- Relaciona las suposiciones, el método y el resultado: confirmo que cada intervalo tiene un inicio menor que su fin y que todos comparten sala y base de tiempo, porque la regla de fusión depende de ese contrato. Con intervalos semiabiertos, un fin igual al siguiente inicio no se solapa. Defino que una entrada vacía da una salida vacía.
- Prueba el caso límite que más importa: para [1,8), [2,3), [8,10) mantengo [1,8) y [8,10), porque el intervalo anidado no puede acortar el fin y ser adyacentes no es solaparse. También pruebo duplicados, un solo intervalo y una entrada vacía, y rechazo los extremos invertidos.
- Explica una comprobación de validación u operativa de la que te encargues: ordenar cuesta O(n log n) y el recorrido es O(n); la salida puede necesitar O(n) de espacio porque todos los intervalos podrían quedar separados. Si la entrada está ordenada de forma garantizada, puedo fusionar en flujo, pero sigo validando el orden o me apoyo en un contrato explícito.