4.13

Idea. Treat each interval (a_i, b_i) as two events: an entry “+1” at time a_i and an exit “−1” at time b_i. Sorting the 2 n events and scanning them once gives the number of people in the room after every chronologically-next change.

Algorithm.
1. E ← empty list
2. for each person i:
   append (a_i, +1) and (b_i, −1) to E
3. sort E by time (O(n log n))
4. cur = 0, best = 0, bestTime = NULL
5. for (t, delta) in E in order:
   cur += delta
   if cur > best: best = cur; bestTime = t
6. return bestTime (moment with maximum attendance)

Correctness proof (sketch).
Because all times are distinct, the sorted event list enumerates every instant when the room’s population changes. The variable cur is exactly the number of people present just after processing each event. Whenever cur exceeds every previous value, the corresponding time is saved; hence bestTime is the first instant at which the maximum simultaneous attendance occurs.

Complexity.
Building the 2 n events is Θ(n). Sorting them costs Θ(n log n). The single linear scan is Θ(n). Thus the overall running time is Θ(n log n) and the extra space Θ(n).

Compact Python implementation.
def busiest_moment(a, b): # lists of entry and exit times
  events = [(t, 1) for t in a] + [(t, -1) for t in b]
  events.sort() # O(n log n)
  cur = best = 0; best_time = None
  for t, d in events: # O(n)
    cur += d
    if cur > best:
      best, best_time = cur, t
  return best_time

Thus, the scan-line (sweep) method gives the required [math]O(n\log n)[/math] algorithm to identify the moment when the party was most crowded.

Back to Chapter 4