Search lands in PR-5.1 (Pagefind).

Data Structures & Algorithms

Sweep Line

Events on a timeline + running counter — the universal template for overlap-count problems.

  1. Problem 01 Sweep Line Template Decompose to events, sort, sweep a running counter. 5 min
  2. Problem 02 Car Pooling Sweep events or difference array; reject as soon as load exceeds capacity. 5 min
  3. Problem 03 Difference Array diff[l] += v; diff[r+1] -= v; prefix-sum to recover values. 5 min