# Intervals — Part 1: The Pattern

Interval problems (meetings, bookings, time ranges, genome segments) almost always start the same way: **sort by start time**, then sweep left to right while comparing each interval with the last one you kept. Sorting costs O(n log n) and the sweep is O(n). Two related tools cover the rest: **sorting by end time** for greedy selection, and a **sweep line over events** (or a min-heap of end times) for "how many overlap at once".

![Sorted intervals merged left to right when they overlap](diagrams/01-merge-intervals.svg)

## 1. The Overlap Test

Two intervals `a = [a0, a1]` and `b = [b0, b1]` overlap when **each starts before the other ends**:

```text
closed  [s, e]:  a0 <= b1 and b0 <= a1      ([1,4] and [4,5] overlap)
half-open [s, e): a0 <  b1 and b0 <  a1      (meetings 9–10 and 10–11 don't conflict)
```

Always ask which convention the problem uses: "does a meeting ending at 10:00 conflict with one starting at 10:00?" The answer changes `<` into `<=`.

After sorting by start, you only need to compare with the **last merged** interval: `start <= last.end`.

## 2. Templates

```typescript
function mergeIntervals(intervals: number[][]): number[][] {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const [start, end] of sorted) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) last[1] = Math.max(last[1], end);
    else merged.push([start, end]);
  }
  return merged;
}

function overlaps(a: number[], b: number[]): boolean {
  return a[0] < b[1] && b[0] < a[1];
}
```

```python
def merge_intervals(intervals):
    intervals = sorted(intervals, key=lambda iv: iv[0])     # 1. sort by start
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:                # 2. overlaps the last one?
            merged[-1][1] = max(merged[-1][1], end)          #    extend it
        else:
            merged.append([start, end])                      #    or start a new one
    return merged

def overlaps(a, b):
    return a[0] < b[1] and b[0] < a[1]                      # half-open [start, end)
```

## 3. Three Strategies

| Question | Strategy | Example |
|---|---|---|
| Merge / union of ranges | sort by **start**, extend the last | Merge Intervals, Insert Interval |
| Keep as many non-overlapping as possible / remove the fewest | sort by **end**, greedily keep the earliest-finishing | Non-overlapping Intervals, arrows |
| How many overlap at the same time (rooms, servers, peak load) | **sweep line** over +1/−1 events, or a min-heap of end times | Meeting Rooms II, car pooling |

**Why sort by end for greedy selection?** The interval that finishes first leaves the most room for everything after it. Any optimal solution can swap its first interval for the earliest-finishing one without losing anything (an exchange argument), so the greedy choice is always safe.

## 4. Sweep Line

Turn each interval into two events, `(start, +1)` and `(end, −1)`, sort them (processing `−1` before `+1` at equal times for half-open intervals), and keep a running count. The maximum running count is the maximum overlap. It generalizes to weighted loads (`+passengers`, `−passengers`) and is the core of calendar and capacity problems.

## Under the Hood: Interval Trees

When intervals arrive dynamically and you must answer "which intervals overlap x?" many times, sorting once isn't enough. An **interval tree** (or a segment tree over coordinates) stores intervals in a balanced BST keyed by start, each node annotated with the maximum end in its subtree, giving O(log n + k) queries. Databases use similar ideas for range indexes (PostgreSQL's GiST indexes on `tsrange`), and calendars use them for conflict checks. In interviews, mentioning this as the follow-up for "what if intervals keep arriving?" is a strong senior signal.

## Common Pitfalls

1. **Not sorting first**, or sorting by the wrong key (start vs end).
2. **Closed vs half-open confusion:** `[1,2]` and `[2,3]` merge if closed, not if half-open.
3. **Forgetting `max` when extending:** `[1,10]` followed by `[2,3]` must stay `[1,10]`.
4. **Mutating the input** when the caller expects it unchanged (sort a copy).
5. **Event order at equal times** in sweep lines: decide whether an end and a start at the same time overlap.

## Quick Reference

```text
Merge: sort by start; if s <= last.end: last.end = max(last.end, e) else push
Greedy keep max non-overlapping: sort by end; keep if s >= lastEnd
Max overlap: events (s,+1),(e,-1); sort; running max   (or min-heap of ends)
O(n log n) for the sort, O(n) sweep
```