Leetcode 57 – Insert Interval – Solução

O problema Leetcode 57, intitulado Insert Interval, ou algo como “Inserção de intervalo” em português é um problema clássico que faz parte da famosa lista Blind 75, que contém problemas comuns em entrevistas de emprego de grandes empresas de tecnologia, como Google, Facebook etc.

Neste post eu irei explicar como resolvê-lo, e irei mostrar a solução usando Python.

Enunciado do problema – Leetcode 57

Lhe é dado um array intervals de intervalos não sobrepostos, em que intervals[i] = [starti, endi] representa o início e o fim do i-ésimo intervalo e os intervalos em intervals são ordenados em ordem ascendente pelo valor de starti. Você também recebe um intervalo newInterval = [start, end] que representa o início e o fim de outro intervalo.

Insira newInterval em intervals de forma que os intervalos ainda estejam ordenadores em ordem ascendente pelo valor de starti e que intervals permaneça sem intervalos sobrepostos (mescle os intervalos sobrepostos, se necessário).

Retorne intervals após a inserção.

---

Exemplo 1:
– Entrada: intervals = [[1,3],[6,9]], newInterval = [2,5]
– Saída: [[1,5],[6,9]]

Exemplo 2:
– Entrada: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
– Saída: [[1,2],[3,10],[12,16]]
– Explicação: Os intervalos do meio são mesclados porque o novo intervalo [4,8] se sobrepõe a [3,5],[6,7] e [8,10], resultando em um grande intervalo de 3 a 10.

Condições:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals é ordernado por starti em ordem ascendente.
• newInterval.length == 2
• 0 <= start <= end <= 105

---

Solução explicada

Para resolver esse problema, é preciso pensar nas possibilidades de inserção de um novo intervalo no array de intervalos existentes. Em suma, há três possibilidades para newInterval:

1. Ele deve ser inserido antes de um outro intervalo em intervals
2. Ele deve ser inserido depois de um outro intervalo em intervals
3. Ele se sobrepõe a outro(s) intervalo(s) em intervals e deve ser mesclado com ele(s).

Analisemos cada um desses casos para tornar as coisas mais claras.

Note também que para essa solução, utilizaremos um array auxiliar chamado result para o qual copiaremos os intervalos do array original conforme as regras discutidas a seguir, e no qual também inseriremos o newInterval.

Inserção do novo intervalo antes de outro intervalo

A primeira opção para o lugar no qual o novo intervalo (newInterval) pode ser inserido é antes de um intervalo já existente no array intervals. Como o array intervals já está ordenado em ordem crescente pelo valor de starti , sabemos que o limite esquerdo do intervalo i + 1 é sempre maior que o limite esquerdo do intervalo i. Sabendo, também, que não há intervalos sobrepostos no array original, podemos concluir o seguinte:

Se encontrarmos um intervalo i no array intervals cujo valor de starti for maior que o valor de end do newInterval, podemos inserir newInterval antes do intervalo i no array auxiliar e copiar para este último o resto do array original

Inserção do novo intervalo depois de outro intervalo

Se o novo intervalo não puder ser inserido antes de um intervalo existente em intervals, a nossa segunda opção é verificar se ele pode ser inserido depois de um intervalo existente. Seguindo a lógica de inserção antes de um outro intervalo, podemos dizer que

Se encontrarmos um intervalo i no array intervals cujo valor de endi for menor que o valor de start do newInterval, podemos inserir newInterval depois do intervalo i no array original.

Todavia, aqui há algo com o que atentar: ao invés de inserir newInterval no array auxiliar result, adicionamos em result o intervalo que acabamos de descobrir vir antes de newInterval. Por que isso? Porque não sabemos ainda se há outros intervalos logo a seguir que podem estar sobrepostos a newInterval, como mostrado na figura a seguir.

Mescla do novo intervalo com outro já existente

Se o novo intervalo não puder inserido nem antes de um intervalo já existente, ou seja, se nenhuma das duas condições são verdadeiras:

1. end < starti (o novo intervalo cabe antes do intervalo existente)
2. start > endi (o novo intervalo cabe depois do intervalo existente)

sabemos que temos em mãos uma sobreposição de intervalos. O que fazer, então? Neste caso, precisamos unir os dois intervalos sobrepostos em um único intervalo, para que no final a sobreposição desapareça. Uma vez os intervalos (newInterval e intervals[i]) mesclados, adicionamos o intervalo resultante no array result.

Código – Python

---

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    out = []

    for i in range(len(intervals)):
        if intervals[i][0] > newInterval[1]:
            out.append(newInterval)
            return out + intervals[i:]
        elif intervals[i][1] < newInterval[0]:
            out.append(intervals[i])
        else:
            newInterval = [min(intervals[i][0], newInterval[0]), max(intervals[i][1], newInterval[1])]
    
    out.append(newInterval)
    return out

---

Note que antes de retornar o array auxiliar out, é preciso adicionar-lhe newInterval ao fim, pois se o programa não se encerrou na linha 7, que dizer que o newInterval é maior que todos os intervalos já existentes no array inicial intervals, ou que a partir de um certo ponto newInterval se sobrepõe a todos os intervalos existentes até o fim da lista intervals.

Conclusão

Espero tê-lo ajudado a entender como resolver o problema Leetcode 57 – Insert Interval. Se você tiver encontrado outra forma de resolver o problema, ou talvez uma forma mais eficiente, por favor me diga nos comentários que eu ficarei feliz em adicioná-la ao conteúdo do texto.

Gostou do artigo? Então inscreva-se na nossa newsletter para não perder nenhum dos nossos artigos 🙂