Intervals — Fundamentals — Data Structures & Algorithms

What is an Interval?

An interval [start, end] represents a continuous range on some axis. In interviews, intervals model three kinds of domains:

Domain	Example	Typical problem
Time	Meetings, cron jobs, booking windows	Meeting Rooms, Calendar
Space	X-coordinates of balloons or segments	Burst Balloons, Skyline
Numeric	Ranges on the integer line	Data Stream, Range Module

Whatever the domain, the underlying algebra is the same — two numbers defining a range, and a question about how that range relates to others.

The four flavors of interval notation

Interval notation

Closed     [a, b]   → includes both endpoints
Open       (a, b)   → excludes both endpoints
Half-open  [a, b)   → includes a, excludes b    ← most common in real systems
Half-open  (a, b]   → excludes a, includes b

The universal overlap formula

Two intervals [a1, a2] and [b1, b2] overlap if and only if:

The one formula you must memorize

            max(a1, b1)  ≤  min(a2, b2)
 
If true:
    Intersection = [ max(a1, b1), min(a2, b2) ]
    Union        = [ min(a1, b1), max(a2, b2) ]
 
If false:
    Gap          = [ min(a2, b2), max(a1, b1) ]

The 6 Interval Relationships

Every pair of intervals falls into exactly one of these six categories. Understanding them visually is the shortcut to writing clean, bug-free code.

① A entirely before B

  A:  ■■■■■
  B:                ■■■■■
      ─────┬────┬───┬────┬─────→
          A.s  A.e B.s  B.e

Condition	`A.end < B.start`
Overlap?	No
Mental model	A finishes before B even begins.

② B entirely before A

  A:                ■■■■■
  B:  ■■■■■
      ─────┬────┬───┬────┬─────→
          B.s  B.e A.s  A.e

Condition	`B.end < A.start`
Overlap?	No — mirror of ①.
After sorting	Impossible — A always starts ≤ B.

③ Partial overlap — A starts first

  A:  ■■■■■■■■■
  B:        ■■■■■■■■■
            ▓▓▓▓▓  ← intersection
      ───┬────┬────┬────┬─────→
         A.s  B.s  A.e  B.e

Condition	`A.start ≤ B.start` AND `A.end ≥ B.start` AND `A.end ≤ B.end`
Merged	`[A.start, B.end]`
Intersection	`[B.start, A.end]`

④ Partial overlap — B starts first

  A:        ■■■■■■■■■
  B:  ■■■■■■■■■
            ▓▓▓▓▓  ← intersection
      ───┬────┬────┬────┬─────→
         B.s  A.s  B.e  A.e

Condition	`B.start ≤ A.start` AND `B.end ≥ A.start` AND `B.end ≤ A.end`
Merged	`[B.start, A.end]`
After sorting	Impossible — same reason as ②.

⑤ A fully contains B

  A:  ■■■■■■■■■■■■■■■
  B:       ■■■■■■■
      ───┬─────────────┬─────→
         A.s  B.s B.e  A.e

Condition	`A.start ≤ B.start` AND `A.end ≥ B.end`
Merged	`[A.start, A.end]` (A already covers B)
Trap	Remember to write `end = max(A.end, B.end)` — it handles this naturally.

⑥ B fully contains A

  A:       ■■■■■■■
  B:  ■■■■■■■■■■■■■■■
      ───┬─────────────┬─────→
         B.s  A.s A.e  B.e

Condition	`B.start ≤ A.start` AND `B.end ≥ A.end`
Merged	`[B.start, B.end]`
After sorting	Becomes: `A.start = B.start` but `B.end > A.end`.

Six cases collapse to three

Mental model — the timeline ruler

Picture intervals as blocks laid out on a ruler. Sorting aligns them left-to-right. Walk right; for each new block ask one question:

“Does it touch or overlap the last block I placed?”

If yes → extend. If no → start a new block. That single model solves Merge Intervals, Employee Free Time, and several other patterns.

Sorting Strategies

The single most important decision in any interval problem is how to sort. The wrong sort order = the wrong answer.

Strategy	Key	Use it for	Problems
Sort by start	`key=x[0]`	Merging, inserting, intersections, conflict detection	#56, #57, #252, #253, #759, #986
Sort by end	`key=x[1]`	Greedy selection — max non-overlapping, min removals, min arrows	#435, #452, Activity Selection
Start ↑, then end ↓	`key=(x[0], -x[1])`	Remove Covered Intervals — process largest span first at each start	#1288
Event-based (sweep)	`key=(x[0], x[1])`	Counting active intervals at any point, peak usage, skyline	#253 alt, #732, #1094, #218

The 6 Common Approaches

Pattern recognition comes from knowing the toolkit. Nearly every interval problem you’ll see reduces to one of these six techniques.

#	Approach	When to reach for it
1	Sort + linear scan	Maintain a “last” interval, compare, merge or start fresh. Solves ~50% of all interval problems.
2	Sweep line (events)	Decompose into start/end events, sort, sweep, keep a running counter. Answers “how many overlap at point X?“
3	Greedy selection	Sort by end, greedily pick the earliest-finishing interval. For optimisation — max kept, min removals, min resources.
4	Priority queue (heap)	Track active intervals by end time in a min-heap. Answers “is any room free?” for resource allocation.
5	Two pointers	Two pre-sorted interval lists — advance the pointer whose interval ends first. Key for intersection problems.
6	Difference array	Bounded-integer coordinates — `O(1)` range updates via `diff[l] += v; diff[r+1] -= v`, then prefix sum to recover values.

Pattern recognition cheat sheet

Universal Edge Cases

Before writing a single line of code, run through this checklist:

#	Scenario	Usual handling
1	Empty input	Return `[]` / `0` / `true` — match the problem’s identity element
2	Single interval	Trivial base case — return as-is
3	All intervals identical	They all merge into one
4	No overlaps at all	Output equals input
5	One giant interval covering everything	Everything merges into it
6	Touching endpoints `[1,2]` & `[2,3]`	Overlap? Depends on closed vs. half-open — clarify
7	Zero-length `[5,5]`	Valid point-interval or degenerate — confirm
8	Negative coordinates	Make sure your math doesn’t assume positives
9	Very large values	Watch for `start + end` overflow on signed 32-bit

The 22 Pattern Map

Every interval problem in this season maps to one of six core techniques. Use this table as your index — the first 11 are the FAANG core, the next 11 are advanced extensions.

Core patterns (1–11)

#	Pattern	LC #	Sort by	Approach
1	Merge Intervals	#56	Start	Sort + linear scan
2	Insert Interval	#57	pre-sorted	Three-phase sweep
3	Meeting Rooms I	#252	Start	Consecutive pair check
4	Meeting Rooms II	#253	Start / events	Min-heap or sweep line
5	Non-Overlapping Intervals	#435	End	Greedy selection
6	Interval List Intersections	#986	pre-sorted	Two pointers
7	Employee Free Time	#759	Start	Merge + find gaps
8	Remove Interval	#1272	pre-sorted	Single pass + remnants
9	My Calendar I	#729	—	Overlap check per booking
10	My Calendar II	#731	—	Two-layer tracking
11	Data Stream as Disjoint Intervals	#352	maintained	Binary search + merge

Advanced patterns (12–22)

#	Pattern	LC #	Sort by	Approach
12	Sweep Line Template	—	Events	`+1 / −1` decomposition
13	Min Arrows to Burst Balloons	#452	End	Greedy group counting
14	My Calendar III	#732	Events	Delta timeline / TreeMap
15	Car Pooling	#1094	Events	Sweep or difference array
16	Range Module	#715	maintained	Insert + Remove composed
17	Meeting Rooms III	#2402	Start	Two heaps (avail + busy)
18	Difference Array	#1109	—	`O(1)` range update + prefix sum
19	The Skyline Problem	#218	Events	Sweep + max-heap
20	Rectangle Area II	#850	Events	2-D sweep + merged y-coverage
21	Interval Tree Template	—	Median	Static BST of intervals
22	Task Scheduler	#621	Frequency	Closed-form math on counts

What is an Interval?

The four flavors of interval notation

The universal overlap formula

The 6 Interval Relationships

① A entirely before B

② B entirely before A

③ Partial overlap — A starts first

④ Partial overlap — B starts first

⑤ A fully contains B

⑥ B fully contains A

Six cases collapse to three

Mental model — the timeline ruler

Sorting Strategies

The 6 Common Approaches

Pattern recognition cheat sheet

Universal Edge Cases

The 22 Pattern Map

Core patterns (1–11)

Advanced patterns (12–22)

Comments