NUHMAN.com

Introduction

LeetCode 56: Merge Intervals is a widely asked coding interview question where you're given a list of intervals, and the task is to merge all overlapping intervals.

This problem is often used to evaluate your understanding of sorting, interval logic, and greedy merging.

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 1:

go

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Intervals [1,3] and [2,6] overlap and are merged into [1,6].

Example 2:

go

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

Constraints

• 1 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10⁴

Approach: Sort and Merge

The approach is simple:

1. Sort the intervals by their starting value.
2. Iterate through the intervals.
3. If the current interval overlaps with the previous one, merge them.
4. If it doesn’t, add the current interval to the result.

Go Implementation

go

import "sort"

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

    // Sort by start time
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

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

    for i := 1; i < len(intervals); i++ {
        last := result[len(result)-1]
        current := intervals[i]

        if current[0] <= last[1] {
            // Merge intervals
            last[1] = max(last[1], current[1])
        } else {
            result = append(result, current)
        }
    }

    return result
}

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

Example Walkthrough

For input [[1,3],[2,6],[8,10],[15,18]]:

• Sort: [[1,3], [2,6], [8,10], [15,18]]
• Merge [1,3] and [2,6] → [1,6]
• No overlap between [1,6] and [8,10]
• Final output: [[1,6], [8,10], [15,18]]

Time and Space Complexity

MetricComplexityTime ComplexityO(n log n)Space ComplexityO(n)

• Sorting takes O(n log n).
• The rest is a linear scan to merge.

Edge Cases

• Intervals already non-overlapping.
• All intervals overlap and become one.
• Single interval → return as is.
• Duplicate intervals.

Key Takeaways

• Sort intervals first to simplify the merge logic.
• Efficient merging uses greedy expansion.
• A go-to solution for many real-world problems (calendar scheduling, event collision, etc.)