Reservas, turnos, interrupções de serviço e promoções são todos intervalos: pares (start, end). Quase todo problema de intervalos começa do mesmo jeito: ordene pelo início. Depois, uma única passada permite comparar cada intervalo com o último que você manteve.
- Dois intervalos ordenados se sobrepõem quando o próximo início vem antes do fim atual. Decida de propósito se intervalos que se tocam, como 9-10 e 10-11, contam como um só; aqui, contam.
- Mesclar significa manter uma lista e então estender o último intervalo ou iniciar um novo.
- As lacunas são os espaços entre os intervalos mesclados.
- O número de salas necessárias é o máximo de intervalos abertos ao mesmo tempo: transforme cada intervalo em um evento +1 no início e um evento -1 no fim, ordene os eventos e acompanhe a contagem acumulada. Processe um fim antes de um início no mesmo horário se uma sala liberada às 10:00 puder ser reutilizada às 10:00.
- Para fazer a interseção de duas agendas, percorra as duas listas ordenadas com dois ponteiros.
Os tempos nesta lição são minutos ou horas em números simples, o que deixa a lógica visível.
Saída: [(9, 12), (13, 16)]. Primeiro os intervalos são ordenados; depois, cada um estende o último ou começa um novo.