Overview

Given the start and end times of multiple meetings, find the maximum number of meetings being held simultaneously (the congestion level).

Analysis

This problem is a classic “interval scheduling” or “event processing” problem. A naive approach would require counting the number of meetings occurring at every time \(t\). However, since the constraint allows \(T\) up to \(10^9\), scanning all time points is not practical (the time complexity would be \(O(TN)\), resulting in TLE).

Instead, we consider “event-based processing.” That is, we treat the starts and ends of meetings as events, process them in chronological order, and dynamically update the number of simultaneous meetings at each moment.

An important note: when start and end events occur at the same time, end events must be processed first. This is to correctly maintain the count in cases where the next meeting begins exactly when the previous one ends.

For example, consider the following two meetings: - Meeting A: [1, 3) - Meeting B: [3, 5)

At time 3, A ends and B begins, so the simultaneous count should be 1. If we processed the start event first, the simultaneous count would temporarily become 2, leading to an incorrect result.

Algorithm

1. For each meeting, create a “+1” event corresponding to the start time \(S_i\) and a “-1” event corresponding to the end time \(E_i\).
2. Sort these events in chronological order. For events at the same time, process end events (-1) before start events (+1).
3. Iterate through the sorted events from the beginning, updating the current simultaneous count current_overlap.
4. After each update, update the maximum value max_overlap.
5. Finally, output max_overlap.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting the events)
• Space complexity: \(O(N)\) (for storing the event list)

Implementation Notes

• Manage start and end events together as tuples (time, +1 or -1).

• By using (time, value) as the sort key, end events are naturally processed before start events at the same time (since -1 < +1).

• To read input efficiently, it is advisable to use sys.stdin.read (especially when there is a large amount of input in Python).

  Source Code

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    T = int(data[1])
    
    events = []
    for i in range(N):
        s = int(data[2 * i + 2])
        e = int(data[2 * i + 3])
        events.append((s, 1))   # 予約開始
        events.append((e, -1))  # 予約終了
    
    # イベントを時刻順にソート（同じ時刻なら終了イベントを先に処理）
    events.sort(key=lambda x: (x[0], x[1]))
    
    max_overlap = 0
    current_overlap = 0
    
    for time, change in events:
        current_overlap += change
        if current_overlap > max_overlap:
            max_overlap = current_overlap
    
    print(max_overlap)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.