Merge Intervals

LeetCode 56 · View on LeetCode

Sort intervals by start time, then merge overlapping ones in a single pass. Two intervals overlap when the current start is within the previous end.

package main

import (
	"fmt"
	"sort"
)

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	merged := [][]int{intervals[0]}
	for _, iv := range intervals[1:] {
		last := merged[len(merged)-1]
		if iv[0] <= last[1] {
			if iv[1] > last[1] {
				last[1] = iv[1]
			}
		} else {
			merged = append(merged, iv)
		}
	}
	return merged
}

func main() {
	fmt.Println(merge([][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}}))
	// [[1 6] [8 10] [15 18]]
	fmt.Println(merge([][]int{{1, 4}, {4, 5}}))
	// [[1 5]]
	fmt.Println(merge([][]int{{1, 4}, {0, 4}}))
	// [[0 4]]
}