Geometry, sweep, simulation, and parsing · HTML
Each object emits start/end events; sort by coordinate and tie rule, and the state after x remains constant until the next coordinate.
Recognition signals
- Interval overlap or peak concurrency
- Natural start and end events
- State is constant between coordinates
- Union length or coverage count is needed
- Geometry can be swept along one axis
False friends
| Signal | Why it is different |
|---|
| Original event order is semantically required | If events cannot be reordered by coordinate, sorting changes the process; use direct simulation. |
| The remaining dimension is dynamically complex | A sweep removes one dimension only; the other may still need a segment tree. |
Core invariant
After all events at x are applied, active exactly represents objects present on the open span (x,next_x).
State, transition, and processing order
| Item | Definition |
|---|
| State | Sorted (x,delta) events, active count or set, objective accumulator, and previous coordinate. |
| Transition | First settle the span from prev to x using old active, then combine every delta at x under one tie policy. |
| Frontier / order | The sweep coordinate separates finalized left space from unprocessed right space; state changes only at events. |
Python skeleton
def max_overlap(half_open_intervals):
events = []
for left, right in half_open_intervals:
if left < right:
events.append((left, 1))
events.append((right, -1))
active = best = 0
# For [left,right), endings at x happen before starts at x.
for _, delta in sorted(events, key=lambda e: (e[0], e[1])):
active += delta
best = max(best, active)
return best
def covered_length(intervals):
events = sorted((x,d) for l,r in intervals for x,d in ((l,1),(r,-1)) if l < r)
active = total = 0; prev = None
for x, delta in events:
if prev is not None and active: total += x-prev
active += delta; prev = x
return total
Correctness sketch
- Activity can change only at an endpoint.
- No event lies between adjacent coordinates, so old active is valid across the whole span.
- Summing all deltas at x produces the exact state for the next open span.
- Every event span is visited once, so peaks and lengths are neither missed nor duplicated.
Complexity
| Time | Space | Parameters |
|---|
| O(E log E) | O(E) | E events, usually a constant multiple of object count |
Edge cases
- Half-open and closed intervals use different tie rules
- Understand same-coordinate events as a batch
- Zero-length intervals
- Negative coordinates
- Settle length before changing active
Error patterns
| Pattern | Why it fails / fix |
|---|
| Wrong same-point order | For half-open intervals, endings precede starts. |
| Updating before settling length | This applies the new state to the span on the left. |
| No explicit tie rule | Peak counts then depend accidentally on sort stability. |
Selection and exclusion rules
- State changes only at endpoints: sweep line.
- Only peak overlap: delta counts suffice.
- The other dimension needs dynamic summaries: combine a segment tree.
- Write interval boundary semantics before choosing ties.
Original micro-example
| Part | Detail |
|---|
| Result | Maximum overlap is 2. |
| Scenario | Half-open intervals [1,4), [2,5), and [4,6). |
| Walkthrough | At coordinate 4 the first interval ends before the third begins, preventing a false count of 3. |
Recall prompts
My notes