Dev Skills
Go·Go for coding rounds

Merge overlapping intervals

Sort by start, then one pass. The sort does the hard part.

Topic 37 of 98 · 5 min to read · 45 min to build
After this topic you can
  • Write interval merging with one sort and one pass.
  • Explain why updating a copy of the last interval does nothing.
  • Predict the merged output for a small input.

The problem

Given intervals like [1,3] [2,6] [8,10], merge the ones that overlap: [1,6] [8,10].

Brute force first

Without sorting: keep comparing every pair of intervals. When two overlap, replace them with their union and start the scan again. Stop when a full pass merges nothing.

Each pass is O(n²) pairs and you may need n passes: O(n³) time worst case, O(n) space. Sorting turns it into one pass.

The approach

Sort by start time. Now an interval either overlaps the last merged one (its start is not after that end), so you extend it, or it starts a new merged interval. O(n log n) time for the sort, O(n) for the output.

intervals.go
package main
import (
	"fmt"
	"sort"
)
// merge combines overlapping [start, end] intervals.
// Sort by start, then each interval either extends the last one or starts a new one.
func merge(in [][2]int) [][2]int {
	if len(in) == 0 {
		return nil
	}
	s := append([][2]int(nil), in...) // copy: do not reorder the caller's slice
	sort.Slice(s, func(i, j int) bool { return s[i][0] < s[j][0] })
	out := [][2]int{s[0]}
	for _, cur := range s[1:] {
		last := &out[len(out)-1] // pointer, so we can grow it in place
		if cur[0] <= last[1] {
			last[1] = max(last[1], cur[1])
		} else {
			out = append(out, cur)
		}
	}
	return out
}
func main() {
	fmt.Println(merge([][2]int{{8, 10}, {1, 3}, {2, 6}, {15, 18}})) // [[1 6] [8 10] [15 18]]
	fmt.Println(merge([][2]int{{1, 4}, {4, 5}}))                    // [[1 5]]
	fmt.Println(merge([][2]int{{1, 10}, {2, 3}}))                   // [[1 10]]
}

Dry run

[1,3] [2,6] [8,10] [15,18], already sorted by start:

intervallast in outoverlap?out after
[1,3](none)-[1,3]
[2,6][1,3]2 <= 3, yes, end = max(3,6)[1,6]
[8,10][1,6]8 > 6, no[1,6] [8,10]
[15,18][8,10]15 > 10, no[1,6] [8,10] [15,18]

Go-specific gotchas

  • `sort.Slice` sorts in place. Copy first if the caller's slice must not change. slices.SortFunc with cmp.Compare is the newer way and also fine.
  • Take a pointer to the last element (&out[len(out)-1]) to update it. last := out[len(out)-1] is a copy, so changing it does nothing.
  • `[2]int` is an array, a value type. It is copied on assignment, which is exactly why the pointer above is needed.
  • Decide whether touching intervals ([1,4] and [4,5]) merge. Here they do, because of <=. Ask.
The short version
  • Sort by start, then one pass.
  • Extend the last interval or start a new one.
  • Update through a pointer or index, not a copy.
Remember: Most interval problems become easy once they are sorted by start.
Build this before moving on
Insert a new interval into an already sorted, non-overlapping list and merge as needed, in O(n) without sorting again.
Coding challenge · checked by tests
Write merge(in [][2]int) [][2]int that merges overlapping intervals (touching ones like [1,4] [4,5] merge too) and returns them sorted by start. Example: [1,3] [8,10] [2,6] → [1,6] [8,10].

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Insert a new interval into an already sorted, non-overlapping list and merge as needed, in O(n) without sorting again.
  2. 2Dry run [1,4] [2,3]. Why must the merge use max(last end, new end) rather than just the new end?
  3. 3Given meeting times, can one person attend all of them? ([0,30] [5,10] [15,20] → no.)
Official documentation
Check yourselfTake the Go for coding rounds test