Intervals, Line Sweep, And Range Updates
Asked of: Software Engineer
Last updated

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 whennext.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-heapplus lazy deletion orTreeMap; emit only height changes. -
Difference array / range add — for update
[l, r] += x, dodiff[l] += x,diff[r+1] -= x, then prefix;O(n + q). -
Range overwrite queries — process updates in reverse with
DSU next-unassignedor interval skipping so each index is assigned once; nearO((n+q) α(n)). -
Boundary convention — decide early whether intervals are closed
[s,e]or half-open[s,e); meeting rooms usually allow reuse whenend <= 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.
Featured in interview prep guides
Practice questions
- Check Digits and Combine RangesGoogle · Software Engineer · Technical Screen · hard
- Compute minimum rooms for time intervalsGoogle · Software Engineer · Technical Screen · easy
- Apply Range Overwrite QueriesGoogle · Software Engineer · Onsite · hard
- Compute minimum number of rooms neededGoogle · Software Engineer · Technical Screen · medium
- Compute city skyline outlineGoogle · Software Engineer · Technical Screen · hard
- Find safe travel intervals between planet influencesGoogle · Software Engineer · Technical Screen · hard
- Compute servers needed for daily recurring jobsGoogle · Software Engineer · Technical Screen · medium
- Count user sessions from logsGoogle · Software Engineer · Onsite · Medium
- Find horizontal cut balancing square areasGoogle · Software Engineer · Onsite · Medium
- Parse strings and find meeting slotsGoogle · Software Engineer · Onsite · Medium
- Solve Banana Speed and Interval MergeGoogle · Software Engineer · Technical Screen · medium
Related concepts
- Interval Merging And Range ManipulationCoding & Algorithms
- Interval, Boundary, And Monotonic Stack AlgorithmsCoding & Algorithms
- Intervals, Sliding Windows, And Time-Ordered StateCoding & Algorithms
- Time Interval Overlap And Sweep-Line AlgorithmsCoding & Algorithms
- Arrays, Intervals, Sliding Windows, And Prefix SumsCoding & Algorithms
- Interval Scheduling And Calendar SystemsCoding & Algorithms