Why This Matters
Intervals model schedules, reservations, memory ranges, time windows, genomic regions, and logs. Many interview questions are really about choosing the right boundary order and maintaining an overlap invariant.
Prerequisite Check
Review Arrays and Sorting. Most interval techniques sort by start time, end time, or event coordinate before scanning.
Learning Objectives
By the end, you should be able to:
- Decide whether intervals are closed, open, or half-open.
- Merge overlapping intervals after sorting by start.
- Detect conflicts and meeting-room counts.
- Use sweep-line events when overlaps matter globally.
- Avoid off-by-one mistakes at touching boundaries.
Core Idea
Sort intervals so local comparisons become meaningful. Keep the current merged range or active count as the scan invariant.
| Pattern | Invariant | Typical problem |
|---|---|---|
| Merge intervals | current range covers all overlaps seen so far | merge ranges |
| Conflict detection | previous end is the latest end of accepted interval | meeting attendance |
| Greedy scheduling | last selected end is as early as possible | maximum non-overlapping intervals |
| Sweep line | active count reflects events crossed so far | rooms, overlaps, coverage |
Visual Model
[1, 4] and [2, 6] overlap -> [1, 6]
[1, 6] and [8, 9] do not overlap -> keep both
The scan works because sorted starts guarantee that only the latest merged end can overlap the next interval.
Non-Example or Failure Mode
If the problem treats intervals as half-open [start, end), then [1, 3) and [3, 5) do not overlap. If it treats them as closed [start, end], they touch at 3. The algorithm must match the boundary convention.
Worked Example
Merge [(1, 4), (2, 6), (8, 9), (9, 10)] as closed intervals.
sort by start -> same order
[1,4] overlaps [2,6] -> [1,6]
[8,9] starts after 6 -> new interval
[9,10] overlaps [8,9] under closed convention -> [8,10]
LeetCode-Style Problem Patterns
| Pattern | Recognition signal | Move |
|---|---|---|
| Merge intervals | "combine overlapping ranges" | sort by start, extend current end |
| Meeting rooms | "minimum rooms/resources" | sweep starts and ends or min-heap by end |
| Non-overlap removal | "erase minimum intervals" | greedy by earliest end |
| Insert interval | "add one interval into sorted list" | copy before, merge overlap, copy after |
Common Mistakes
| Mistake | Correction |
|---|---|
| Ignoring endpoint convention. | Decide closed vs half-open before comparing boundaries. |
| Sorting by the wrong key. | Merge usually sorts by start; greedy scheduling often sorts by end. |
| Comparing only adjacent original intervals. | Sort first so adjacency has meaning. |
| Mutating input unexpectedly. | Copy or document mutation. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What is an interval in these problems? | A range with start and end under a stated boundary convention. |
| Example / non-example | Do [1,3) and [3,5) overlap? | No under half-open semantics. |
| Computation | What dominates merge-interval complexity? | Sorting: O(n log n). The scan is O(n). |
| Proof | Why does sorted-by-start merging need only the current merged end? | Any future interval starts no earlier than the current one. |
| Transfer | When should interval problems use a heap? | When tracking many active end times, such as meeting rooms. |
Exercises
Beginner:
- Merge three overlapping intervals by hand.
- Decide whether two half-open intervals conflict.
- Sort intervals by start and by end; explain the difference.
Intermediate:
- Implement meeting-room conflict detection.
- Solve maximum non-overlapping intervals greedily by earliest end.
Challenge:
- Implement a sweep-line maximum-overlap counter and state how ties are handled.
Diagram Recommendation
Type: timeline merge trace.
Caption: "Sorted interval starts let one current end summarize the active merge."
Purpose: Expose endpoint conventions and overlap decisions visually.
Implementation Task
Implement closed-interval merge and half-open conflict detection. Notice that the overlap comparisons differ.
Run interval merge and conflict checks
This cell checks closed merge behavior and half-open meeting conflicts.
Output will appear here.
Next Topics
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- Princeton Algorithms, Sorting: https://algs4.cs.princeton.edu/20sorting/
- Python documentation, sorting HOWTO: https://docs.python.org/3/howto/sorting.html