4.15

Algorithm (sweep-line)
1. For every interval [math](l_i,r_i)[/math] create two events:   • (l_i , +1)  (start of an interval)   • (r_i , –1)  (end of an interval, inclusive)
2. Sort the 2n events by coordinate; if two events share the same coordinate, process all +1 events before any –1 events (so an endpoint belongs to its interval).
3. Scan the ordered events keeping
  cnt – current number of intervals covering the sweep point
  best – maximum value of cnt seen so far
  p – coordinate where that maximum first occurs
  

cnt = 0, best = 0
for (x,delta) in events:
    cnt += delta
    if cnt > best:
        best = cnt
        p = x

4. When the loop ends, p is a point contained in [math]best[/math] intervals – the maximum possible.

Correctness
• The sweep maintains cnt as the exact number of intervals covering the current coordinate because each start increases and each (inclusive) end later decreases the count.
• Whenever cnt exceeds all previous values, that coordinate is by definition covered by the largest number of intervals seen so far; storing it guarantees the final p achieves the global maximum.

Complexity
Building the event list takes [math]O(n)[/math]; sorting 2n keys takes [math]O(n\log n)[/math]; the scan is linear. Total: [math]O(n\log n)[/math] time and [math]O(n)[/math] space.

Example (input from prompt) – events after sorting:
(10,+1)(15,+1)(20,+1)(40,-1)(50,+1)(60,-1)(70,-1)(90,-1)
Running the scan reaches cnt=3 first at coordinate 50, so [math]p=50[/math] covered by three intervals, matching the sample.

Back to Chapter 4