Skip to content

Volume ITechnology

4.27.0 — Intervals: The Pattern ​

Recognition cue. The input is pairs of (start, end) — meetings, bookings, ranges, tasks with deadlines.

The move. Sort first. Almost every interval problem is one sort followed by one linear sweep. The only real decision is what to sort by.

The decision that solves the chapter ​

you wantsort bywhy
merge overlapping intervalsstartany overlapping interval must begin inside the one you are building
most non-overlapping intervals to keependfinishing earliest leaves the most room for everything after
fewest removals to remove all overlapsendsame problem, counted the other way
fewest points to stab every intervalendsame computation again
maximum concurrency / roomseither — use a sweep line or a heapyou are counting, not choosing

Sorting by start is for merging. Sorting by end is for choosing. Getting that backwards is the most common interval mistake, so carry it as one sentence.

The overlap condition ​

Two intervals [a,b] and [c,d] overlap when:

a \le d \quad\text{and}\quad c \le b

Each starts before the other ends. The negation is often easier to use: they are disjoint when b < c or d < a.

Always ask whether touching counts as overlapping. It flips < to <= and the problems disagree with each other:

  • Merge Intervals — [1,4] and [4,5] do merge.
  • Meeting Rooms and Non-overlapping Intervals — [1,2] and [2,3] do not conflict.

Two adjacent problems, opposite conventions. Ask every time.

The sweep line ​

The most transferable idea here. Turn each interval into two events and sort them:

python
events = []  # (1)
for start, end in intervals:
    events.append((start, +1))  # (2)
    events.append((end, -1))  # (3)
events.sort()          # (4) ties: (t, -1) sorts before (t, +1), so ends process first

count = best = 0  # (5)
for _, delta in events:
    count += delta  # (6)
    best = max(best, count)  # (7)

The template, line by line. This is the sweep line: walk through time and keep a running count. (1) A list of events. (2) Each interval's start is an event that adds 1 to the count of open intervals, and (3) its end is an event that subtracts 1. (4) Sort the events by time. When a start and an end share a time, -1 sorts before +1, so the end is processed first and touching intervals do not count as overlapping. (5) The number open right now, and the most ever open together. (6) Apply each event in time order. (7) Keep the highest count. That is, for example, the number of meeting rooms needed.

The tie-break is deliberate. At equal times the -1 must come first, so a resource freed at time 10 is available to something starting at 10.

It solves maximum concurrency, car pooling, double bookings, the skyline problem, and capacity planning in real systems.

When the coordinate range is small and bounded, replace the sort with a difference array: add 1 at each start, subtract at each end, then take a prefix sum. O(n + T) instead of O(n \log n) — the bounded-values trick from 4.4.5.

The six problems ​

#ProblemSort byThe one insight
4.27.1Insert Interval ★already sortedThree groups: before, overlapping, after
4.27.2Merge Intervals ★startmax(last_end, end) — a contained interval must not shrink it
4.27.3Non-overlapping Intervals ★endKeep the most; remove the rest
4.27.4Meeting Rooms ★startSorted neighbours are enough
4.27.5Meeting Rooms II ★sweep or heapThe answer is the maximum concurrency
4.27.6Minimum Interval per QuerybothOffline — sort the queries too

★ marks the Blind 75 subset.

The traps on this pattern ​

Forgetting max when merging. A fully contained interval would shrink the merged range.

Sorting by start when you should sort by end. Merging versus choosing.

Assuming the touching convention. Ask.

JavaScript's default sort. [[10,20],[9,15]] sorts as strings without a comparator.

Sorting when the input is already sorted. Insert Interval is O(n) precisely because it is not sorted again.

What the interviewer will push on ​

"Sort by start or by end, and why?" Merging versus choosing, with the exchange argument for the end case: finishing earliest leaves the most room.

"State the overlap condition." a <= d and c <= b.

"Does touching count?" Ask, and say why it matters.

"How do you count maximum concurrency?" The sweep line, with the tie-break explained.

"What if intervals arrive one at a time?" An ordered map or an interval tree, O(\log n) per insertion, instead of re-sorting.

One thing to volunteer: say the sort-by rule as your opening line. It is the whole chapter in one sentence, and it tells the interviewer you recognise the family rather than the problem.

Recall

  • Sort first. Sort by start to merge; sort by end to choose the most non-overlapping.
  • Overlap: a <= d and c <= b. Always ask whether touching counts — Merge Intervals says yes, Meeting Rooms says no.
  • Merging needs max(last_end, end), or a contained interval shrinks the result.
  • "Keep the most non-overlapping" is the activity selection greedy, proved by exchange: finishing earliest leaves the most room.
  • Maximum concurrency = sweep line. Two events per interval, sorted, with ends processed before starts at equal times.
  • Bounded coordinates → a difference array instead of a sort.
  • Insert Interval is O(n) because the input is already sorted; Merge Intervals is O(n \log n) because it is not.
  • When all queries are known in advance, sorting them (offline processing) often turns an impossible problem into a sweep.

Next: 4.27.1 Insert Interval — three groups, three loops, no branching.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet