Interval Merging And Range Manipulation

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 current end; 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 if next.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.