Skip to main content

Checkpoint: The Busiest Moment

Challenge on lesson: Checkpoint — The Sweep Discipline

CHALLENGE
Difficulty: advanced+25 XP

**Task.** n intervals [l, r] with integer endpoints (1 ≤ l ≤ r ≤ 10^9). The intervals are closed: [1,3] and [3,5] both contain point 3. Print the maximum number of intervals sharing a single point. **Constraints:** 1 ≤ n ≤ 200000. **Budget check:** one sort of 2n events plus one sweep: O(n log n). Any per-point probing of the coordinate space is a wrong family (coordinates reach 10^9).

Back to lesson: Checkpoint — The Sweep Discipline