LeetEye LeetEye
Medium Intervals ~5 min

Merge Intervals

intervals merge-intervals

Problem

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Examples

Example 1
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
[1,3] and [2,6] overlap, merge into [1,6].
Example 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
[1,4] and [4,5] overlap (touch at 4).
Key Insight

Sort by start time. Then merge consecutive intervals if they overlap.

Sort by start. For each interval, if it overlaps with result's last (start <= last_end), merge. Otherwise, add new.

How to Approach This Problem

Pattern Recognition: When you see keywords like merge intervals intervals, think Intervals.

Step-by-Step Reasoning

1 Sorting by start time ensures:
Answer: Overlapping intervals become adjacent
If sorted by start, interval can only overlap with its predecessor in result.
2 After sorting, [a, b] overlaps with [c, d] (where c >= a) if:
Answer: b >= c
Since intervals are sorted, c >= a. Overlap if previous end >= current start.
3 When merging [a, b] with overlapping [c, d]:
Answer: [a, max(b, d)]
Since sorted, a <= c. So start is a. End is the farther of b and d.
4 Start a new merged interval when:
Answer: Current doesn't overlap with result's last
No overlap means current interval is separate. Add it to result.
5 [1,4] and [4,5] should:
Answer: Merge to [1,5]
They touch at 4. Typically treated as overlapping (b >= c means 4 >= 4).

Solution

def merge(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []
    
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    result = [intervals[0]]
    
    for i in range(1, len(intervals)):
        # If overlaps with last in result
        if intervals[i][0] <= result[-1][1]:
            result[-1][1] = max(result[-1][1], intervals[i][1])
        else:
            result.append(intervals[i])
    
    return result

Complexity Analysis

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

Master This Pattern

Build intuition with interactive MCQs. Practice Intervals problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye