56. Merge Intervals

Medium

Problem Description

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]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def merge(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []
    
    # Sort intervals based on start time
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    
    for interval in intervals[1:]:
        if interval[0] <= merged[-1][1]:
            # Overlapping intervals, update end time
            merged[-1][1] = max(merged[-1][1], interval[1])
        else:
            # Non-overlapping interval, add to result
            merged.append(interval)
    
    return merged

Java Solution


class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }
        
        // Sort intervals based on start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        List merged = new ArrayList<>();
        merged.add(intervals[0]);
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= merged.get(merged.size() - 1)[1]) {
                // Overlapping intervals, update end time
                merged.get(merged.size() - 1)[1] = 
                    Math.max(merged.get(merged.size() - 1)[1], intervals[i][1]);
            } else {
                // Non-overlapping interval, add to result
                merged.add(intervals[i]);
            }
        }
        
        return merged.toArray(new int[merged.size()][]);
    }
}

C++ Solution


class Solution {
public:
    vector> merge(vector>& intervals) {
        if (intervals.empty()) {
            return {};
        }
        
        // Sort intervals based on start time
        sort(intervals.begin(), intervals.end());
        
        vector> merged;
        merged.push_back(intervals[0]);
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] <= merged.back()[1]) {
                // Overlapping intervals, update end time
                merged.back()[1] = max(merged.back()[1], intervals[i][1]);
            } else {
                // Non-overlapping interval, add to result
                merged.push_back(intervals[i]);
            }
        }
        
        return merged;
    }
};

JavaScript Solution


/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if (!intervals.length) {
        return [];
    }
    
    // Sort intervals based on start time
    intervals.sort((a, b) => a[0] - b[0]);
    
    const merged = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= merged[merged.length - 1][1]) {
            // Overlapping intervals, update end time
            merged[merged.length - 1][1] = 
                Math.max(merged[merged.length - 1][1], intervals[i][1]);
        } else {
            // Non-overlapping interval, add to result
            merged.push(intervals[i]);
        }
    }
    
    return merged;
};

C# Solution


public class Solution {
    public int[][] Merge(int[][] intervals) {
        if (intervals == null || intervals.Length <= 1) {
            return intervals;
        }
        
        // Sort intervals based on start time
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        
        var merged = new List();
        merged.Add(intervals[0]);
        
        for (int i = 1; i < intervals.Length; i++) {
            if (intervals[i][0] <= merged[merged.Count - 1][1]) {
                // Overlapping intervals, update end time
                merged[merged.Count - 1][1] = 
                    Math.Max(merged[merged.Count - 1][1], intervals[i][1]);
            } else {
                // Non-overlapping interval, add to result
                merged.Add(intervals[i]);
            }
        }
        
        return merged.ToArray();
    }
}

Complexity Analysis

Solution Explanation

This solution uses a sorting-based approach to merge overlapping intervals:

Key points: