Intervals, Line Sweep, and Difference Arrays

What's being tested

These problems test interval scheduling, line sweep, and difference arrays for detecting overlaps, allocating the minimum resources, and applying many range updates efficiently. You must demonstrate precise endpoint semantics, deterministic tie-breaking, and the ability to replace repeated simulation with sorting or prefix-sum reconstruction.

Patterns & templates

• Half-open intervals [start, end) overlap iff max(starts) < min(ends); touching endpoints such as [1,3) and [3,5) do not conflict.

• Line sweep: sort starts and ends, process equal timestamps according to semantics; release resources before assigning arrivals for reusable half-open intervals.

• Minimum resources: sort intervals by start time and maintain a min-heap of active end times; heap size is peak concurrency, with O(n log n) time.

• Deterministic assignment: keep reusable vehicle IDs in a min-heap; assign the smallest available ID, while returning vehicles before processing same-time pickups.

• Grouped recurring jobs: merge or union intervals by job identifier before capacity counting when repeated occurrences represent one logical resource requirement.

• 2D difference array: for inclusive rectangle [r1,r2] × [c1,c2], update four corners, then take 2D prefix sums; total work is O(n² + q).

• Coordinate compression maps sparse endpoints to ranks, reducing memory from grid or time range size to O(n + q); preserve interval boundaries carefully.

Common pitfalls

Pitfall: Treating inclusive and half-open endpoints interchangeably creates false conflicts or misses reuse at an exact return/pickup time.

Pitfall: Simulating every cell for every rectangle costs O(qn²); mark boundaries once and reconstruct with prefix sums.

Pitfall: Ignoring stable tie-breaking can produce a numerically correct fleet size but an incorrect vehicle assignment.

Practice these

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