Q17: Merge Intervals. - DSA Patterns (Multi-Lang)

In Simple Words: Sort intervals by start time. Iterate through: if current interval overlaps with previous (curr[0] <= prev[1]), merge them by setting prev[1] = max(prev[1], curr[1]); else push as new interval.

Time: $O(N \log N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        prev_end = merged[-1][1]
        if start <= prev_end:
            merged[-1][1] = max(prev_end, end)
        else:
            merged.append([start, end])
    return merged