Skip to main content

🟨 Merge Intervals (#56)

🔗 Problem Link​

📋 Problem Statement​

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]]

Example 2​

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

🔑 Key Insights & Approach​

Core Observation: Sort by start time, then merge overlapping intervals.

Why Sort?

  • O(n log n) time for sort
  • O(1) or O(n) space depending on sort
  • Simple linear scan after sorting

Pattern: "Sort and Merge" for intervals.

🐍 Solution: Python​

Approach: Sort and Merge​

Time Complexity: O(n log n) | Space Complexity: O(n)

from typing import List

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)):
            if intervals[i][0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], intervals[i][1])
            else:
                merged.append(intervals[i])

        return merged

🔵 Solution: Golang​

Approach: Sort and Merge​

Time Complexity: O(n log n) | Space Complexity: O(n)

import "sort"

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return [][]int{}
    }

    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    merged := [][]int{intervals[0]}

    for i := 1; i < len(intervals); i++ {
        last := len(merged) - 1

        if intervals[i][0] <= merged[last][1] {
            merged[last][1] = max(merged[last][1], intervals[i][1])
        } else {
            merged = append(merged, intervals[i])
        }
    }

    return merged
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

📚 References​