Interval Merging And Range Manipulation
Asked of: Software Engineer
Last updated

What's being tested
This tests the interval merging pattern: sort ranges, scan once, and maintain the last merged range while deciding overlap, adjacency, or separation. Interviewers probe boundary reasoning, especially closed vs half-open intervals, contiguous ranges, nested intervals, empty input, and O(n log n) vs O(n) tradeoffs when input is already sorted.
Patterns & templates
-
Sort-and-scan merge — sort by
start, then extend currentend;O(n log n)time,O(n)output space. -
Insertion into sorted intervals — copy intervals before
newInterval, merge overlaps, then append the rest;O(n)when already sorted. -
Adjacency rule — for closed intervals, merge if
next.start <= cur.end + 1; for half-open intervals, merge ifnext.start <= cur.end. -
Overlap predicate — two ranges overlap when
a.start <= b.end && b.start <= a.end; adjust carefully for half-open[start, end). -
Canonical output invariant — maintain sorted, non-overlapping, non-adjacent merged intervals after every append or update.
-
Deletion / subtraction — split an interval into left and right remainders around the removed range; handle full coverage and no-overlap cases.
-
Complexity clarity — if input is unsorted, sorting dominates; if pre-sorted, merging is linear and usually constant auxiliary space excluding output.
Common pitfalls
Pitfall: Treating adjacent intervals inconsistently, such as merging
[1,3]and[4,5]without confirming whether adjacency should count.
Pitfall: Mutating the input interval objects directly when the interviewer expects a fresh result or when aliasing can corrupt later comparisons.
Pitfall: Forgetting edge cases: empty list, one interval, nested intervals, duplicate starts, negative bounds, and integer overflow from
end + 1.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Merge overlapping and adjacent rangesAmazon · Software Engineer · Onsite · Medium
- Insert and merge an intervalAmazon · Software Engineer · Onsite · Medium
- Solve interval deletion and GCD subarray problemsAmazon · Software Engineer · Technical Screen · Medium
- Merge overlapping intervalsAmazon · Software Engineer · Technical Screen · Medium
Related concepts
- Intervals, Line Sweep, And Range UpdatesCoding & Algorithms
- Interval, Boundary, And Monotonic Stack AlgorithmsCoding & Algorithms
- Arrays, Intervals, Sliding Windows, And Prefix SumsCoding & Algorithms
- Time Interval Overlap And Sweep-Line AlgorithmsCoding & Algorithms
- Intervals, Sliding Windows, And Time-Ordered StateCoding & Algorithms
- Interval Scheduling And Calendar SystemsCoding & Algorithms