Handbooks / Data Structures & Algorithms / Chapter 7

Intervals and Sweep Line

7 pages · ~5 min✓ Reviewed

Builds on Trees and Graphs. Next up: Dynamic Programming and Greedy.

Data Structures & AlgorithmsPage 1

Intervals: Overlap and Sort-First Mental Model

1. Overlap Test

Interval = [start, end]
a and b overlap iff a.start <= b.end AND b.start <= a.end
Touching endpoints [1,2],[2,3]: the statement decides

Problem	[1,2],[2,3]	Compare
Merge	overlap	`<=`
Meeting rooms	no overlap	`<`

2. Sort First

SortO(n log n)
Scan onceO(n)
Compare with previousor running end

Data Structures & AlgorithmsPage 2

Merge Intervals and Insert Interval

1. Merge: Sort, Then Scan

Data Structures & AlgorithmsPage 3

Meeting Rooms with a Min-Heap

1. Meeting Rooms I

Data Structures & AlgorithmsPage 4

Sweep Line with Events

1. Events and Running Sum

Data Structures & AlgorithmsPage 5

Non-Overlapping Intervals by End Time

1. Goal and Greedy

Data Structures & AlgorithmsPage 6

Intervals Cheat Sheet

1. Overlap, Merge, Insert

Data Structures & AlgorithmsPage 7

Goal	Sort by
Merge, insert, count rooms	start
Maximize kept intervals	end

Touching ends	Process first
No overlap ([1,2],[2,3])	-1 then +1
Counts as overlap	+1 then -1

Problem	Keep test	Answer
Activity selection	`start >= lastEnd`	kept
Burst balloons	`start > lastEnd` (touching overlaps)	kept = arrows
By start order	on overlap drop larger end	`lastEnd = min(lastEnd, end)`

Intervals and Sweep Line

Intervals: Overlap and Sort-First Mental Model

1. Overlap Test

2. Sort First

Merge Intervals and Insert Interval

1. Merge: Sort, Then Scan

Meeting Rooms with a Min-Heap

1. Meeting Rooms I

Sweep Line with Events

1. Events and Running Sum

Non-Overlapping Intervals by End Time

1. Goal and Greedy

Intervals Cheat Sheet

1. Overlap, Merge, Insert

Check yourself

3. Pick the Key

2. Insert Interval (sorted input, O(n))

3. Common Bugs

2. Meeting Rooms II: the Heap

3. Example and Cost

2. Ties at Equal Time

3. Two Pointers and Heap

2. Why End Time

3. Variants

2. Meeting Rooms

3. Removals and Keys

Problem	Sort by	Time
Merge	start	O(n log n)
Insert	already sorted	O(n)
Rooms	start	O(n log n)
Max keep	end	O(n log n)