Merge Intervals (with Gaps)

Problem

Given a list of intervals, merge all overlapping intervals and return the merged list. Also return the total length of the gaps between the merged intervals.

Example

[[1, 3], [2, 6], [8, 10]]
  Merged: [[1, 6], [8, 10]]
  Gaps:   2          (the gap from 6 to 8)

Go Solution

package main

import (
    "fmt"
    "sort"
)

func mergeIntervals(intervals [][]int) ([][]int, int) {
    if len(intervals) == 0 {
        return nil, 0
    }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    merged := [][]int{{intervals[0][0], intervals[0][1]}}
    for _, iv := range intervals[1:] {
        last := merged[len(merged)-1]
        if iv[0] <= last[1] { // overlaps -> extend
            if iv[1] > last[1] {
                last[1] = iv[1]
            }
        } else { // disjoint -> start a new interval
            merged = append(merged, []int{iv[0], iv[1]})
        }
    }

    gaps := 0
    for i := 1; i < len(merged); i++ {
        gaps += merged[i][0] - merged[i-1][1]
    }
    return merged, gaps
}

func main() {
    m, g := mergeIntervals([][]int{{1, 3}, {2, 6}, {8, 10}})
    fmt.Println(m, g) // [[1 6] [8 10]] 2
}

How to Solve

1. Sort by start. Once intervals are ordered by their left edge, any interval that overlaps the current group must start before that group ends.
2. Sweep and extend. Keep the last merged interval. If the next one starts at or before last[1], they overlap — extend last[1] to the larger right edge. Otherwise it is disjoint, so append it as a new interval.
3. Sum the gaps afterwards. Between consecutive merged intervals the gap is merged[i][0] - merged[i-1][1]. Adding these up gives the total gap length.

Complexity

Time: O(n log n), dominated by the sort. Space: O(n) for the merged output (O(1) extra beyond it).