24 de Março
Mesclar intervalos
Como ordenar por início e transformar vários intervalos em uma passada que decide se expande o bloco atual ou abre outro.
Intervalos Intermediario 20 min TypeScript
Dado um array de intervalos intervals, onde intervals[i] = [starti, endi], faca o merge de todos os intervalos que se sobrepoem e retorne um array com os intervalos finais.
Intervalos que encostam também contam como sobrepostos.
Exemplo:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
O que perceber antes de codar
- Depois de ordenar por início, a unica sobreposição relevante e com o ultimo intervalo consolidado.
- Se dois intervalos encostam, como `[1,4]` e `[4,5]`, eles viram um bloco só.
- No merge, o que normalmente muda e o fim do intervalo.
Erros comuns
- esquecer de ordenar antes da passada
- atualizar o fim com o valor atual direto em vez de usar `max`
Passo 1 - Escrever a versão inicial que nasce naturalmente
Se você ainda não conhece o padrão, a tendencia e:
- pegar um intervalo
- comparar com todos os blocos que já juntou
- decidir se encaixa em algum deles
Funciona.
Mas faz comparação demais.
Passo 2 - Perguntar qual comparação realmente importa
O problema não pede descobrir sobreposição em ordem aleatoria.
Ele pede consolidar tudo no final.
Se os intervalos estiverem ordenados por início, o único candidato real a sobrepor o intervalo atual e o ultimo intervalo da resposta.
Passo 3 - Entender a regra do merge
Com dois intervalos:
- se
currentStart <= lastEnd, eles se sobrepoem - o início do bloco continua o mesmo
- o fim vira
max(lastEnd, currentEnd)
Senao, você abre um novo bloco.
Passo 4 - Transformar isso em varredura linear
Depois de ordenar, a passada fica simples:
- se sobrepoe, expande
- se não sobrepoe, adiciona novo
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function merge(intervals: number[][]): number[][] {
// sua solução aqui
return []
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n log n)
Espaço: O(n)
Solução 1 - Comparar com todos os merges existentes em O(n²)
Boa versão inicial para deixar visível o trabalho extra.
export function merge(intervals: number[][]): number[][] {
const merged: number[][] = []
for (const [start, end] of intervals) {
let currentStart = start
let currentEnd = end
const nextMerged: number[][] = []
for (const [mergedStart, mergedEnd] of merged) {
const overlaps = currentStart <= mergedEnd && mergedStart <= currentEnd
if (overlaps) {
currentStart = Math.min(currentStart, mergedStart)
currentEnd = Math.max(currentEnd, mergedEnd)
} else {
nextMerged.push([mergedStart, mergedEnd])
}
}
nextMerged.push([currentStart, currentEnd])
nextMerged.sort((a, b) => a[0] - b[0])
merged.length = 0
merged.push(...nextMerged)
}
return merged
}Correta, mas desorganizada demais para um problema que escorrega rápido para O(n²).
Solução 2 - Ordenação + varredura linear em O(n log n)
Agora a regra local fica clara.
export function merge(intervals: number[][]): number[][] {
if (intervals.length === 0) {
return []
}
const sorted = [...intervals].sort((a, b) => a[0] - b[0])
const merged = [sorted[0].slice()]
for (let index = 1; index < sorted.length; index += 1) {
const [currentStart, currentEnd] = sorted[index]
const lastMerged = merged[merged.length - 1]
if (currentStart <= lastMerged[1]) {
lastMerged[1] = Math.max(lastMerged[1], currentEnd)
} else {
merged.push([currentStart, currentEnd])
}
}
return merged
}O truque não e decorar Merge Intervals. E perceber que a ordenação transforma um problema global numa decisão local repetida.
O que dizer na entrevista
Uma explicação curta e boa seria:
Sem ordenar, eu acabo comparando cada intervalo com vários blocos já consolidados. Quando ordeno por início, só preciso olhar para o ultimo intervalo consolidado. Se houver sobreposição, eu expando o fim. Se não houver, eu abro um bloco novo. O custo total fica
O(n log n)por causa da ordenação.
Isso mostra que você:
- usou estrutura antes de iterar
- reduziu comparações de forma justificavel
- explicou a regra do merge sem enrolacao
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- ordenar e fazer sweep
- consolidar blocos que se sobrepoem
- comparar o estado atual só com o ultimo estado valido
- resolver meeting rooms, insert interval e variações parecidas
O ponto não e decorar
merge.
O ponto e aprender quando a ordenação elimina a necessidade de comparar com todo mundo.