Intervals, Line Sweep, And Range Updates

What's being tested

These problems test interval reasoning: detecting overlap, merging ranges, assigning resources, and applying many updates without touching every element each time. Interviewers are probing whether you can convert ranges into events, sort boundaries correctly, and choose between heap, line sweep, difference array, or reverse processing based on constraints.

Patterns & templates

• Merge intervals — sort by start, maintain current [lo, hi]; merge when next.start <= hi, otherwise emit; O(n log n) time.

• Meeting rooms with min-heap — sort by start, pop rooms whose end <= start, push current end; heap size is answer; O(n log n).

• Line sweep events — convert intervals to (time, delta) events, sort with correct tie-breaking; prefix sum gives active count or resource demand.

• Skyline sweep — process building start/end events, track active heights using max-heap plus lazy deletion or TreeMap; emit only height changes.

• Difference array / range add — for update [l, r] += x, do diff[l] += x, diff[r+1] -= x, then prefix; O(n + q).

• Range overwrite queries — process updates in reverse with DSU next-unassigned or interval skipping so each index is assigned once; near O((n+q) α(n)).

• Boundary convention — decide early whether intervals are closed [s,e] or half-open [s,e); meeting rooms usually allow reuse when end <= start.

Common pitfalls

Pitfall: Sorting starts before ends at the same coordinate can overcount overlaps for half-open intervals like [1,3) and [3,5).

Pitfall: For skyline, emitting every event creates duplicate points; only append when the current maximum height actually changes.

Pitfall: Applying each range update directly is O(nq) and will time out; look for prefix sums, lazy structures, or reverse assignment.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.