Medium

Merge Intervals

073

Given intervals, return overlapping intervals merged and sorted by start.

EXAMPLES

Example 1

Input
{
  "intervals": [
    [
      1,
      3
    ],
    [
      2,
      6
    ],
    [
      8,
      10
    ],
    [
      15,
      18
    ]
  ]
}

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

FUNCTION SHAPE

intervals: intMatrix→intMatrix

SOLUTION NOTE

We sort the intervals by start time, and then iterate. If the current segment starts before the end of the current segment (the last one in res) then we overlap, and so we can extend the current segment in res. Otherwise, if there is no overlap (case 9) we are starting a new segment and can safely add this new segment to res.

Reveal reference solution +

pythonREFERENCE

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort()
    res = []
    for s, e in intervals:
        if res and s <= res[-1][1]:
            res[-1][1] = max(res[-1][1], e)
        else:
            res.append([s, e])
    return res

# Alternative using overlap formula
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort()
    res = []
    for s, e in intervals:
        if res and max(s, res[-1][0]) <= min(e, res[-1][1]):
            res[-1][1] = max(res[-1][1], e)
        else:
            res.append([s, e])
    return res

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗