Explicar a mesclagem de intervalos
Linden Rooms precisa mesclar as reservas sobrepostas de uma sala. A entrada contém intervalos semiabertos em minutos inteiros [start, end), e intervalos adjacentes devem continuar separados. Explique um algoritmo e percorra seus casos limite em voz alta.
Rubrica e preparaçãoO que uma resposta de nível mid cobre · 3 lições para se preparar
Pleno padrão
- Relacione as suposições, o método e o resultado: confirmo que cada intervalo tem um início menor que o seu fim e que todos compartilham a mesma sala e a mesma base de tempo, porque a regra de mesclagem depende desse contrato. Com intervalos semiabertos, um fim igual ao início seguinte não se sobrepõe. Defino que uma entrada vazia resulta em uma saída vazia.
- Teste o caso de borda que mais pesa: para [1,8), [2,3), [8,10), mantenho [1,8) e [8,10), porque o intervalo aninhado não pode encurtar o fim e ser adjacente não é se sobrepor. Também testo duplicatas, um único intervalo e uma entrada vazia, e rejeito extremos invertidos.
- Explique uma verificação de validação ou de operação pela qual você seja responsável: ordenar custa O(n log n) e a varredura é O(n); a saída pode precisar de O(n) de espaço porque todos os intervalos podem ficar separados. Se a entrada tiver ordenação garantida, posso mesclar em fluxo, mas ainda valido a ordem ou me apoio em um contrato explícito.