Pular para o conteúdo

Merge Intervals

Aula 2 de 4 · 5 min

Merge Intervals

Passo 1 de 8

Quatro intervalos, já ordenados pelo início: 1–3, 2–6, 8–10, 9–11.

A ideia

Ordene pelo início e mantenha exatamente um bloco aberto.

Se o próximo intervalo começa antes do fim do bloco aberto, ou exatamente nele, os dois se tocam: estique o fim até o maior dos dois. Senão há um vão, então feche o bloco e abra outro. Cada intervalo é olhado uma vez.

Exemplo do mundo real

As paradas rastreadas de um motorista em uma folha de ponto. Três janelas de GPS sobrepostas no depósito devem aparecer como um só bloco de tempo no depósito, não três — as sobreposições são ruído do sensor, e mesclá-las gera o fato que você realmente cobra.

O código

Sua vez

Coloque os passos em ordem.

  1. Se ele começar no fim aberto ou antes, estique esse fim até o maior dos dois fins
  2. Ordene os intervalos pelo início
  3. Senão há um vão, então abra um novo bloco com este intervalo
  4. Coloque o primeiro intervalo na saída como bloco aberto
  5. Percorra o resto, comparando cada início com o fim do bloco aberto

Mini quiz

1 / 3

Depois de ordenar, quando o próximo intervalo é mesclado ao bloco aberto?