#04MediumAlgorithms · 49% acceptance

Merge Overlapping Intervals

SortingIntervalsGreedy

Given a list of intervals `[start, end]`, merge all overlapping intervals and return the minimal set of non-overlapping intervals that covers the same span.

This is exactly the logic behind merging overlapping peaks or genomic features — formalized.

Examples

Input: [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Note: [1,3] and [2,6] overlap and merge into [1,6].

Constraints

·1 ≤ intervals.length ≤ 10^4
·start ≤ end for every interval.

Hints

solution.pyPython 3

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

Test console

// hit Run to execute the sample tests

// Interactive editor preview. Live code execution arrives with your early-access cohort.