How to Merge Overlapping Intervals in Go

Problem

The task is to merge a collection of intervals so that any overlapping or adjacent intervals are combined into a single continuous interval.

Approach

First, sort all intervals in ascending order of their left (start) boundary. After sorting, adjacent intervals can be examined sequentially: if the current interval’s start is less than or equal to the previous interval’s end, the two intervals overlap and should be merged; otherwise, the previous interval is finalized and the current interval becomes the new reference.

Implementation Details

The Go implementation follows these steps:

func merge(intervals [][]int) [][]int {
    // 1. Sort intervals by their left boundary
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    var result [][]int
    // 2. Initialize the previous interval
    pre := intervals[0]
    for index := 1; index < len(intervals); index++ {
        // 3. Current interval
        cur := intervals[index]
        // 4. If current start <= previous end, intervals overlap
        if cur[0] <= pre[1] {
            // 5. Merge by taking the larger right boundary
            pre[1] = max(pre[1], cur[1])
        } else {
            // 6. No overlap: store previous interval and move forward
            result = append(result, pre)
            pre = cur
        }
    }
    // 7. Append the last processed interval
    result = append(result, pre)
    return result
}

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

The algorithm relies on the sort.Slice function to order intervals, then uses a linear scan to build the merged list, achieving O(n log n) time due to sorting and O(1) extra space aside from the output.

Illustration