Merge Intervals

Problem statement

You get a list of closed intervals [start, end]. Merge every pair that overlaps (or touches in the usual inclusive sense) so the result is a minimal set of non-overlapping intervals covering the same ranges.

Example:

Input:

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

Expected output:

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

Why: [1, 3] and [2, 6] overlap, so they become [1, 6].

Practice on LeetCode: Merge Intervals

Golang Solution

Sort intervals by start. Walk once, keeping a growing answer list: if the next interval starts before or at the current end, extend that end; otherwise append a new interval.

Time: O(n log n) — sorting dominates
Space: O(n) — output (plus sort overhead depending on the runtime)

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

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

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

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

        // Overlapping
        if answer[last][1] >= intervals[i][0] {
            answer[last][1] = max(answer[last][1], intervals[i][1])
        } else {
            // Non-overlapping
            answer = append(answer, intervals[i])
        }
    }

    return answer
}