Overview

Given \(N\) meeting reservations, the problem asks to find the maximum number of meetings happening simultaneously (congestion level).

Analysis

Naive Approach and Its Problems

The simplest method is to count the number of ongoing meetings at each time from \(0\) to \(T-1\). However, since \(T\) can be as large as \(10^9\), approaches with \(O(T \times N)\) or \(O(T)\) complexity will not meet the time limit.

Key Insight

The number of simultaneous meetings changes only at meeting start times or meeting end times. At all other times, the count remains unchanged.

For example, with 3 meetings \((0, 5), (2, 8), (4, 6)\): - Time 0: Meeting 1 starts → simultaneous count 1 - Time 2: Meeting 2 starts → simultaneous count 2 - Time 4: Meeting 3 starts → simultaneous count 3 (maximum) - Time 5: Meeting 1 ends → simultaneous count 2 - Time 6: Meeting 3 ends → simultaneous count 1 - Time 8: Meeting 2 ends → simultaneous count 0

Thus, there are at most \(2N\) times we need to consider.

Algorithm

We use the event-based sweep line method.

1. Record events: For each meeting, record \(+1\) at the start time and \(-1\) at the end time.

   • Start time \(S_i\): One meeting begins
   • End time \(E_i\): One meeting ends

2. Sort by time: Sort all event times in ascending order.

3. Calculate cumulative sum: Process events in sorted order, computing the cumulative sum to find the simultaneous count at each time.

4. Track maximum: Update the maximum value during the cumulative sum calculation.

Example: Meetings (0,5), (2,8), (4,6)

Events: +1 at time 0, +1 at time 2, +1 at time 4, -1 at time 5, -1 at time 6, -1 at time 8

Cumulative sum:
Time 0: 0+1=1
Time 2: 1+1=2
Time 4: 2+1=3 ← maximum
Time 5: 3-1=2
Time 6: 2-1=1
Time 8: 1-1=0

Answer: 3

Complexity

• Time complexity: \(O(N \log N)\)
  • Recording events: \(O(N)\)
  • Sorting times: \(O(N \log N)\) (at most \(2N\) times)
  • Computing cumulative sum: \(O(N)\)
• Space complexity: \(O(N)\)
  • At most \(2N\) entries in the dictionary storing events

Implementation Notes

1. Using defaultdict: When multiple starts/ends occur at the same time, defaultdict(int) allows natural addition.

2. Order of starts and ends: When a start and end occur at the same time, this implementation adds +1 and -1 to the same key, which cancel out. The problem states that “end time is not included,” so a meeting ending at time \(t\) and a meeting starting at time \(t\) are not counted as simultaneous, and this implementation handles this correctly.

3. Effect of coordinate compression: Even though \(T\) can be as large as \(10^9\), we only process at most \(2N\) times, enabling efficient computation.

Source Code

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    # Event-based coordinate compression approach
    # +1 at start time, -1 at end time, calculate simultaneous count using cumulative sum
    events = defaultdict(int)
    
    for i in range(N):
        S = int(input_data[idx]); idx += 1
        E = int(input_data[idx]); idx += 1
        events[S] += 1
        events[E] -= 1
    
    # Sort event times and calculate cumulative sum
    sorted_times = sorted(events.keys())
    
    max_count = 0
    current_count = 0
    
    for time in sorted_times:
        current_count += events[time]
        max_count = max(max_count, current_count)
    
    print(max_count)

solve()

---

This editorial was generated by claude4.5opus.