Interview conceptCoding & Algorithms

Interval Sweep Line And Merge Algorithms

Asked of: Software Engineer

Last updated

Horizontal trace showing intervals sorted, converted to sweep events, counted for maximum overlap, and merged transitively with correct endpoint handling.

What's being tested

These problems test the interval sweep-line pattern: converting interval starts and ends into ordered events to count concurrent activity, or sorting intervals to merge overlaps. You must handle touching boundaries, chained overlaps, arbitrary input order, and clearly justify O(n log n) time and O(n) space.

Patterns & templates

  • Sweep line: create (+1) start and (-1) end events, sort by time, accumulate an active counter, and track its maximum.

  • For equal timestamps, process starts before ends when intervals are closed; process ends first for half-open intervals [start, end).

  • Merge intervals: sort pairs by start, extend the current interval while next.start <= current.end, otherwise emit and reset.

  • Parallel start/end lists require pairing by index before sorting; never sort the lists independently because that destroys interval identity.

  • Chained overlaps merge transitively: update current.end = max(current.end, next.end) rather than replacing it.

  • Sorting dominates both solutions: O(n log n) time and O(n) auxiliary space; a bounded integer-time domain may enable counting.

  • Define empty input, zero-length intervals, touching endpoints, reversed ranges, and whether output intervals should preserve or normalize boundaries.

Common pitfalls

Pitfall: Sorting starts and ends separately, or comparing only adjacent original inputs, loses interval pairing and misses chained overlaps.

Pitfall: Mishandling equal timestamps changes whether touching intervals count as simultaneous; state the endpoint convention before coding.

Pitfall: Reporting only the algorithm without invariants—explain that the active count equals starts processed minus ends processed.

Practice these

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

Practice questions

Related concepts