Search lands in PR-5.1 (Pagefind).
Explanation Intermediate

Chapter 1 Updated

Intervals — Fundamentals

Core mental models, sorting tricks, and overlap detection logic behind every interval problem.

  • Full 12m
  • Revision 3m
  • Flow 2m

What an interval is

The shape of the data.

  • An interval [start, end] is a continuous range — time, space, or number line.
  • Closed [a, b] is LeetCode’s default; half-open [a, b) is the real-world default (Google Calendar, cron).
  • Touching endpoints [1, 2] + [2, 3] — overlap in closed semantics, adjacent (no overlap) in half-open. Always clarify.

The universal overlap formula

One expression, zero case splits.

  • Two intervals overlap iff max(a1, b1) ≤ min(a2, b2).
  • Intersection = [max(a1, b1), min(a2, b2)]; union = [min(a1, b1), max(a2, b2)].
  • This single formula handles all 6 relationship cases — memorise it.
  • It’s the foundation of ~80% of interval solutions.

Sort-first rule

The decision that makes or breaks the solution.

  • Sort by start → merge, insert, intersection, conflict detection.
  • Sort by end → greedy (max non-overlapping, min removals, min arrows).
  • Sort (start↑, end↓) → process largest-span first at each start (remove covered).
  • Event sort → sweep line for “how many active at this point?”.
  • Rule of thumb: “maximize/minimize a count” → sort by end; “merge/combine” → sort by start.

After sorting, 6 cases → 3 cases

Why the code is so short.

  • Sorting by start makes “B starts first” impossible, collapsing cases ② and ④.
  • Remaining cases: no overlap (A.end < B.start), partial overlap, containment.
  • Partial overlap + containment collapse into one line: merged_end = max(A.end, B.end).
  • Mental model — intervals as blocks on a ruler; walk right, extend or start fresh.

Five recurring approaches

Map the problem to one of these.

  • Sort + linear scan — ~50% of interval problems.
  • Sweep line (events) — “how many active at any point?”.
  • Greedy selection — sort by end, pick earliest-finishing.
  • Priority queue / min-heap — resource allocation, “is any room free?”.
  • Two pointers — two already-sorted interval lists (intersections).

Universal edge-case checklist

Ask these before you code.

  • Empty input, single interval, all-identical, no-overlap-at-all, one-giant-interval.
  • Touching endpoints — clarify closed vs half-open.
  • Zero-length [5, 5] — valid or degenerate?
  • Negative coordinates; integer overflow in start + end.

Comments

Comments are disabled in this environment. Set PUBLIC_GISCUS_REPO, PUBLIC_GISCUS_REPO_ID, and PUBLIC_GISCUS_CATEGORY_ID to enable.