Merge Intervals

Medium

The problem

You get a list of ranges [start, end] in any order. Combine every group of overlapping ranges into one and return the result sorted by start. Ranges that only touch at one point count as overlapping.

Example 1
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
[1, 3] and [2, 6] overlap, so they merge into [1, 6].
Example 2
Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
They touch at 4, which counts as overlapping.
Example 3
Input: intervals = [[8, 10], [1, 2], [2, 3]]
Output: [[1, 3], [8, 10]]
The input is not sorted. [1, 2] and [2, 3] touch at 2.

Limits

1 ≤ len(intervals) ≤ 100,000
start ≤ end for every range

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

If the list is sorted by start, an interval can only overlap the one just before it.

The idea

Sort by start. Keep a result list; if the current start ≤ last end, extend last end with max; else append.

Target: O(n log n) time

Go function shape

func merge(intervals [][]int) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// Merge: merge all overlapping intervals.
func Merge(intervals [][]int) [][]int {
	sorted := slices.Clone(intervals)
	slices.SortFunc(sorted, func(a, b []int) int { return cmp.Compare(a[0], b[0]) })

	out := [][]int{}
	for _, cur := range sorted {
		last := len(out) - 1
		if last < 0 || out[last][1] < cur[0] { // gap: no overlap
			out = append(out, []int{cur[0], cur[1]})
		} else { // overlap (touching counts): extend the end
			out[last][1] = max(out[last][1], cur[1])
		}
	}
	return out
}

Read the lesson: Intervals