Time Interval Overlap And Sweep-Line Algorithms

What's being tested

These problems test interval arithmetic and sweep-line algorithms for time-based concurrency, payroll, and distinct-entity counting. Interviewers are probing whether you handle half-open intervals, boundary tie-breaking, duplicate IDs, partial-hour math, and complexity tradeoffs without overcomplicating the implementation.

Patterns & templates

• Sweep line with events — create (time, delta) pairs, sort by time, accumulate active count; O(n log n) time, O(n) space.

• Tie-breaking for half-open intervals — for [start, end), process end events before start events at the same timestamp to avoid false overlap.

• Distinct active entities — use Map<id, count> or Set<id> when one driver/dasher can have overlapping sessions; don’t just sum intervals.

• Fixed 24-hour window — clamp intervals to [windowStart, windowEnd) before creating events; discard intervals with start >= end after clamping.

• Difference array for bounded time — if timestamps are minute/second-indexed within 24 hours, use prefix sums in O(T + n) instead of sorting.

• Partial-hour pay math — compute duration as end - start, multiply by rate per unit time; avoid rounding until final output unless specified.

• Binary search over sorted intervals/events — for repeated “active at time t” queries, preprocess starts/ends and answer with starts <= t - ends <= t style counts.

Common pitfalls

Pitfall: Treating intervals as closed [start, end] makes a driver ending at 10:00 overlap one starting at 10:00.

Pitfall: Counting sessions instead of unique drivers/dashers overstates concurrency when the same entity has duplicate or overlapping intervals.

Pitfall: Rounding each partial hour independently can introduce payroll errors; accumulate exact minutes/seconds first.

Practice these

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