5.4 Intervals

Deep Dive: The Three Core Interval Operations

Beginner tip: Interval problems deal with time ranges, like meeting schedules. The first step is ALWAYS to sort the intervals. Then: to merge overlapping meetings, sort by start time. To find the maximum number of non-overlapping meetings, sort by end time (greedy). To count simultaneous meetings, use the sweep line technique.

Insert Interval -- Three Phases

Intervals: [[1,2],[3,5],[6,7],[8,10],[12,16]], new: [4,8]

Phase 1 (before new): [1,2] ends before 4 starts -> keep. [3,5] overlaps!
Phase 2 (merge): [3,5] overlaps [4,8] -> merge to [3,8]
                 [6,7] overlaps [3,8] -> merge to [3,8]
                 [8,10] overlaps [3,8] -> merge to [3,10]
                 [12,16] starts after 10 -> STOP merging
Phase 3 (after new): [12,16] -> keep

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

Meeting Rooms II -- Sweep Line

Meetings: [[0,30],[5,10],[15,20]]

Convert to events:
  (0, START), (5, START), (10, END), (15, START), (20, END), (30, END)

Sort by time (END before START if same time):
  0:+1  5:+1  10:-1  15:+1  20:-1  30:-1

Sweep: 1  2  1  2  1  0
Peak concurrent = 2 -> need 2 rooms.

Interval Intersection -- Two Pointers

A: [[0,2],[5,10],[13,23],[24,25]], B: [[1,5],[8,12],[15,24],[25,26]]

i=0 j=0: [0,2] & [1,5] -> overlap [1,2]. A ends first -> i++
i=1 j=0: [5,10] & [1,5] -> overlap [5,5]. B ends first -> j++
i=1 j=1: [5,10] & [8,12] -> overlap [8,10]. A ends first -> i++
i=2 j=1: [13,23] & [8,12] -> no overlap (13>12). B ends first -> j++
i=2 j=2: [13,23] & [15,24] -> overlap [15,23]. A ends first -> i++
i=3 j=2: [24,25] & [15,24] -> overlap [24,24]. B ends first -> j++
i=3 j=3: [24,25] & [25,26] -> overlap [25,25]. done.

---

Before You Start -- How to Think About Interval Problems

The Two Sorting Strategies

Sort by START TIME -> Merge overlapping intervals
  Two intervals overlap if: current.start <= prev.end
  Merge: new_end = max(prev.end, current.end)

Sort by END TIME -> Maximum non-overlapping / minimum removals (greedy)
  Always pick the interval that ends earliest = leaves most room.

Overlap Detection

Two intervals [a, b] and [c, d] overlap if: a < d AND c < b
(Neither starts after the other ends)

No overlap if: b <= c OR d <= a
(One ends before the other starts)

When You See an Interval Problem, Ask Yourself

1. "Merge overlapping" -> Sort by start, merge if overlap
2. "Minimum rooms / maximum concurrent" -> Sort events (start/end), sweep line
3. "Maximum non-overlapping" -> Sort by end, greedy pick
4. "Insert interval" -> Find overlap region, merge, keep rest
5. "Intersection of two lists" -> Two pointers, advance the one that ends first

The Sweep Line Technique (Meeting Rooms II)

Instead of thinking about intervals, think about EVENTS:
  Each interval creates a +1 event (start) and a -1 event (end).
  Sort all events by time.
  Sweep left-to-right, tracking the running count.
  Maximum running count = answer.

Problems

#	Problem	Status
1	Merge Intervals	[ ]
2	Insert Interval	[ ]
3	Non-overlapping Intervals	[ ]
4	Meeting Rooms I & II	[ ]
5	Minimum Number of Arrows to Burst Balloons	[ ]
6	Interval List Intersections	[ ]

Framework

Sort by START TIME -> Merge overlapping
Sort by END TIME   -> Maximum non-overlapping (greedy)

Notes