LeetCode 56 — Merge Intervals

Segundo problema de Intervals — el más fundamental. Sort + scan linear. Patrón maestro de todo el bloque.

Enunciado

Array de intervalos. Fusiona los solapados y devuelve la lista resultante.

---

Solución — Sort + scan

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])
        result = [intervals[0]]
        for start, end in intervals[1:]:
            if start <= result[-1][1]:           # solapan
                result[-1][1] = max(result[-1][1], end)
            else:
                result.append([start, end])
        return result

Análisis: O(n log n).

---

Conexiones

• Próximo: 435-non-overlapping-intervals.

Estado

• Leído
• Implementado desde cero
• Resuelto en LeetCode