Given a list of intervals where each interval is [start, end], merge every group of overlapping intervals and return the resulting non-overlapping intervals sorted by start. Intervals that only touch at an end point, like [1,4] and [4,5], also count as overlapping.
[1,3] and [2,6] overlap, so they become [1,6].- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= start <= end <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Comparing every pair and merging repeatedly is O(n^2) or worse. After sorting by start time, overlapping intervals sit next to each other: if the next interval starts after the current block ends, no later interval (which starts even later) can touch the block either. So one pass is enough: either extend the last merged block or start a new one.
Algorithm
- Sort the intervals by start.
- Put the first interval into
res. - For each next
[s, e]: ifs <= res[-1][1], setres[-1][1] = max(res[-1][1], e). - Otherwise append
[s, e]as a new block. Returnres.
O(n log n) for the sortSpace: O(n) for the outputmax when extending: for [[1,4],[2,3]] the inner interval must not shrink the block to [1,3].class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) res = [] for s, e in intervals: if res and s <= res[-1][1]: res[-1][1] = max(res[-1][1], e) # extend the current block else: res.append([s, e]) # start a new block return res