Merge Intervals

IntervalsArraysSorting

20 min

Problem Statement

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

Example

Example 1:

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

Initial Intervals:

[1, 3]

[2, 6]

[8, 10]

[15, 18]

Result:

[1, 6]

[8, 10]

[15, 18]

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

Solution

To merge overlapping intervals, we first need to sort them by their start time. This ensures that we can process them in order and easily identify overlaps with the most recently processed interval.

Algorithm Steps

Sort the intervals based on their start times.
Initialize a result list with the first interval.
Iterate through the rest of the intervals.
If the current interval overlaps with the last one in the result list, merge them by updating the end of the last interval.
Otherwise, add the current interval to the result list.

Intervals

[1, 6]

[8, 10]

[2, 6]

[15, 18]

Merged Result

Start with the unsorted intervals.

Merge Intervals Solution


class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        if not intervals:
            return []

        intervals.sort(key=lambda x: x[0])
        
        merged = [intervals[0]]
        
        for i in range(1, len(intervals)):
            last_merged = merged[-1]
            current = intervals[i]
            
            if current[0] <= last_merged[1]:
                last_merged[1] = max(last_merged[1], current[1])
            else:
                merged.append(current)
                
        return merged