Intervals & sweep line

Every interval problem in one place: the overlap test, when to sort by start and when by end, inserting into a sorted list, intersecting two lists, counting concurrent events with a sweep line or a heap, and difference arrays for loads over time.

The overlap test#

Two intervals do not overlap when one ends before the other starts. Negate that and you get the only overlap test you need:

// closed intervals: [1,5] and [5,8] share the point 5
overlaps := a[0] <= b[1] && b[0] <= a[1]
// half-open intervals (meetings): [1,5) and [5,8) do not overlap
overlaps = a[0] < b[1] && b[0] < a[1]

Sort by start, or sort by end?#

Goal	Sort by	Why
merge overlapping intervals, insert, detect any conflict	start	overlapping intervals become neighbors
most non-overlapping intervals, fewest arrows, fewest removals	end	taking whatever ends earliest leaves the most room (greedy)
count how many overlap at once	events (each start and end)	the sweep line sees every change in the count

Merging and the greedy "keep the earliest end" proof are covered in the Greedy & intervals lesson. This lesson covers the rest of the family.

Insert into a sorted list in O(n)#

The list is already sorted and non-overlapping, so re-sorting is wasted work. Walk it once in three phases: copy everything that ends before the new interval starts, absorb everything that overlaps by widening the new interval, and copy the rest.

phase	intervals	new interval after
before	[1,2]	[4,8]
absorb	[3,5] [6,7] [8,10]	[3,10]
after	[12,16]

Result: [[1 2] [3 10] [12 16]].

Intersect two sorted lists with two pointers#

Two people's free times, each sorted and non-overlapping. Their common time at any step is [max(starts), min(ends)] if that range isn't empty. Then advance whichever interval ends first: it can't meet anything later in the other list, while the longer interval still might.

The sweep line: how many at once?#

"Minimum meeting rooms," "maximum concurrent users," "most overlapping intervals": all three ask for the peak number of intervals active at one time. Turn each interval into two events: +1 at its start, −1 at its end. Sort the events by time and add them up. The running total is how many intervals are active, and its maximum is the answer.

The tie rule matters. Meetings are half-open, so when one ends at 10 and another starts at 10, process the end first: the room is freed and reused.

Drawing diagram…

Run the trace

sweep_trace.go

package main
 
import (
	"cmp"
	"fmt"
	"slices"
)
 
func main() {
	meetings := [][2]int{{0, 30}, {5, 10}, {15, 20}, {10, 15}}
	type event struct{ time, delta int }
	var events []event
	for _, m := range meetings {
		events = append(events, event{m[0], +1}, event{m[1], -1})
	}
	// By time; at equal times the end (-1) comes first, so a room freed at 10 can be reused at 10.
	slices.SortFunc(events, func(a, b event) int {
		return cmp.Or(cmp.Compare(a.time, b.time), cmp.Compare(a.delta, b.delta))
	})
	rooms, best := 0, 0
	for _, e := range events {
		rooms += e.delta
		best = max(best, rooms)
		fmt.Printf("t=%2d %+d  in use=%d  max=%d\n", e.time, e.delta, rooms, best)
	}
}

Output

t= 0 +1  in use=1  max=1
t= 5 +1  in use=2  max=2
t=10 -1  in use=1  max=2
t=10 +1  in use=2  max=2
t=15 -1  in use=1  max=2
t=15 +1  in use=2  max=2
t=20 -1  in use=1  max=2
t=30 -1  in use=0  max=2

cmp.Or returns its first non-zero argument, which makes multi-key comparisons a single line: compare by time, and only if the times are equal, by delta.

The heap version

When the follow-up is "which room does each meeting get?", events aren't enough. Sort meetings by start and keep a min-heap of end times for the rooms in use. If the earliest-ending room is free by the time the next meeting starts, pop it; then push the new meeting's end. The heap's final size is the number of rooms, and the heap tells you exactly which room was reused.

Difference arrays: loads over a small range#

When coordinates are small integers (bus stops 0..1000, days of a year), skip the sort. Add +p at the index where a load starts and −p where it ends, then run a prefix sum: each position now holds the total load at that point. This is O(n + range) and has no tie rules to get wrong, because ending at stop 5 and starting at stop 5 cancel in the same cell.

stop	0	1	2	3	4	5	6	7
diff for trips (2: 1→5), (3: 3→7)	0	+2	0	+3	0	−2	0	−3
running load	0	2	2	5	5	3	3	0

The peak is 5, so a car with capacity 4 fails and one with capacity 5 works.

The full program#

intervals.go

package main
 
import (
	"cmp"
	"container/heap"
	"fmt"
	"slices"
)
 
// overlaps reports whether closed intervals a and b share at least one point.
func overlaps(a, b [2]int) bool {
	return a[0] <= b[1] && b[0] <= a[1]
}
 
// merge combines every overlapping interval. Sort by start.
func merge(iv [][2]int) [][2]int {
	slices.SortFunc(iv, func(a, b [2]int) int { return cmp.Compare(a[0], b[0]) })
	var out [][2]int
	for _, cur := range iv {
		if n := len(out); n > 0 && cur[0] <= out[n-1][1] {
			out[n-1][1] = max(out[n-1][1], cur[1])
		} else {
			out = append(out, cur)
		}
	}
	return out
}
 
// insert adds one interval to a sorted, non-overlapping list in O(n): before, overlapping, after.
func insert(iv [][2]int, nw [2]int) [][2]int {
	var out [][2]int
	i := 0
	for i < len(iv) && iv[i][1] < nw[0] { // ends before the new one starts
		out = append(out, iv[i])
		i++
	}
	for i < len(iv) && iv[i][0] <= nw[1] { // overlaps: absorb it
		nw[0] = min(nw[0], iv[i][0])
		nw[1] = max(nw[1], iv[i][1])
		i++
	}
	out = append(out, nw)
	return append(out, iv[i:]...)
}
 
// intersect walks two sorted lists with one pointer each.
func intersect(a, b [][2]int) [][2]int {
	var out [][2]int
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		lo, hi := max(a[i][0], b[j][0]), min(a[i][1], b[j][1])
		if lo <= hi {
			out = append(out, [2]int{lo, hi})
		}
		if a[i][1] < b[j][1] { // drop whichever ends first
			i++
		} else {
			j++
		}
	}
	return out
}
 
// minArrows: fewest points that touch every interval. Sort by end.
func minArrows(iv [][2]int) int {
	if len(iv) == 0 {
		return 0
	}
	slices.SortFunc(iv, func(a, b [2]int) int { return cmp.Compare(a[1], b[1]) })
	arrows, at := 1, iv[0][1]
	for _, cur := range iv[1:] {
		if cur[0] > at { // this one is not hit by the last arrow
			arrows++
			at = cur[1]
		}
	}
	return arrows
}
 
// minRooms with a sweep over +1/-1 events. Meetings are half-open [start, end).
func minRooms(iv [][2]int) int {
	type event struct{ time, delta int }
	events := make([]event, 0, 2*len(iv))
	for _, m := range iv {
		events = append(events, event{m[0], 1}, event{m[1], -1})
	}
	slices.SortFunc(events, func(a, b event) int {
		return cmp.Or(cmp.Compare(a.time, b.time), cmp.Compare(a.delta, b.delta))
	})
	rooms, best := 0, 0
	for _, e := range events {
		rooms += e.delta
		best = max(best, rooms)
	}
	return best
}
 
// endHeap holds the end times of meetings currently using a room.
type endHeap []int
 
func (h endHeap) Len() int           { return len(h) }
func (h endHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h endHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *endHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *endHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}
 
// minRoomsHeap: sort by start; reuse the room that frees up earliest if it is free in time.
func minRoomsHeap(iv [][2]int) int {
	slices.SortFunc(iv, func(a, b [2]int) int { return cmp.Compare(a[0], b[0]) })
	h := &endHeap{}
	for _, m := range iv {
		if h.Len() > 0 && (*h)[0] <= m[0] {
			heap.Pop(h) // that room is free again
		}
		heap.Push(h, m[1])
	}
	return h.Len()
}
 
// carPooling with a difference array: +p where passengers board, -p where they leave.
func carPooling(trips [][3]int, capacity int) bool {
	var diff [1001]int // stops are 0..1000
	for _, t := range trips {
		diff[t[1]] += t[0]
		diff[t[2]] -= t[0]
	}
	load := 0
	for _, d := range diff {
		load += d
		if load > capacity {
			return false
		}
	}
	return true
}
 
// freeTime: gaps between busy intervals of everyone, after merging.
func freeTime(schedules [][][2]int) [][2]int {
	var all [][2]int
	for _, s := range schedules {
		all = append(all, s...)
	}
	merged := merge(all)
	var out [][2]int
	for i := 1; i < len(merged); i++ {
		if merged[i-1][1] < merged[i][0] {
			out = append(out, [2]int{merged[i-1][1], merged[i][0]})
		}
	}
	return out
}
 
func main() {
	fmt.Println(overlaps([2]int{1, 5}, [2]int{5, 8}), overlaps([2]int{1, 4}, [2]int{5, 8}))
	fmt.Println(merge([][2]int{{8, 10}, {1, 3}, {2, 6}, {15, 18}}))
	fmt.Println(insert([][2]int{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, [2]int{4, 8}))
	fmt.Println(intersect([][2]int{{0, 2}, {5, 10}, {13, 23}, {24, 25}}, [][2]int{{1, 5}, {8, 12}, {15, 24}, {25, 26}}))
	fmt.Println(minArrows([][2]int{{10, 16}, {2, 8}, {1, 6}, {7, 12}}))
	meetings := [][2]int{{0, 30}, {5, 10}, {15, 20}, {10, 15}}
	fmt.Println(minRooms(meetings), minRoomsHeap(meetings))
	fmt.Println(carPooling([][3]int{{2, 1, 5}, {3, 3, 7}}, 4), carPooling([][3]int{{2, 1, 5}, {3, 3, 7}}, 5))
	fmt.Println(freeTime([][][2]int{{{1, 2}, {5, 6}}, {{1, 3}}, {{4, 10}}}))
}

Output

true false
[[1 6] [8 10] [15 18]]
[[1 2] [3 10] [12 16]]
[[1 2] [5 5] [8 10] [15 23] [24 24] [25 25]]
2
2 2
false true
[[3 4]]

Complexity#

Problem	Time	Space
merge	O(n log n)	O(n)
insert into sorted list	O(n)	O(n)
intersect two sorted lists	O(n + m)	O(n + m) output
fewest arrows	O(n log n)	O(1) extra
meeting rooms, sweep or heap	O(n log n)	O(n)
difference array	O(n + range)	O(range)
employee free time	O(N log N), N = all intervals	O(N)

Recognizing the pattern#

Words like interval, meeting, booking, schedule, overlap, range [l, r], or trip from a to b mean this lesson. Then decide what is asked: one merged list (sort by start), a maximum set without overlaps (sort by end), or a peak count (sweep). If the follow-up is "intervals arrive one at a time" (My Calendar), keep them in a balanced BST keyed by start and check only the neighbors of the new interval; see Balanced BSTs & ordered sets.

Summary#

Two intervals overlap when a.start ≤ b.end && b.start ≤ a.end; use < for half-open intervals.
Sort by start to merge, insert or detect conflicts; sort by end for the greedy "most intervals kept" family.
Insert into a sorted list in three linear phases instead of re-sorting.
Intersect two sorted lists with two pointers, advancing whichever interval ends first.
Peak concurrency is a sweep over +1/−1 events with ends first at ties, or a min-heap of end times when you need room assignments.
With small integer coordinates, a difference array plus a prefix sum avoids sorting.