JuniorJunior (1–3 yrs)CodingPythonMetaGoogleAmazon

Merge Intervals

Given intervals [start, end], merge all overlapping intervals and return the non-overlapping set covering the input.

Answers use simple, clear English.

Time: O(n log n)Space: O(n)

Quick interview answer

Sort by start. Scan: if current starts ≤ last.end, extend last.end; else append a new interval. O(n log n) from sort.

Detailed answer

Sort by start. Scan: if current starts ≤ last.end, extend last.end; else append a new interval. O(n log n) from sort. Clarify half-open vs closed intervals if touching endpoints should merge.

Full explanation

Clarify half-open vs closed intervals if touching endpoints should merge.

Real example & use case

Calendar system collapsing overlapping meeting holds into busy blocks.

Pros & cons

Pros: simple after sort. Cons: sort dominates; streaming needs different structures.

Code example

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

Practice code · python (view only · no execution)

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

#intervals#sorting