Overview

Given the start times \(S_i\) and end times \(E_i\) of \(N\) meetings, the problem asks to find the maximum number of meetings that overlap at any instant (maximum simultaneous usage).

Key Observation

The most important point to note in this problem is that the time range \(T\) can be as large as \(10^9\), which is extremely large.

If \(T\) were small, we could prepare an array from time \(0\) to \(T\) and apply the “imos method” (prefix sum technique), but with \(T = 10^9\), this would result in memory overflow or time limit exceeded (TLE). Therefore, we leverage the property that “the number of simultaneous usages changes only at the moments when a meeting starts or ends.”

By treating the start and end of each meeting as “events” and focusing only on the times when events occur, we can perform the computation independently of the size of \(T\).

Algorithm

We solve this using a technique called event sorting.

1. Creating the event list: For each reservation, create the following two events and store them in a single list:
   • A meeting starts at time \(S_i\): (S_i, 1)
   • A meeting ends at time \(E_i\): (E_i, -1)
2. Sorting: Sort all \(2N\) events in ascending order of time (earliest first).
3. Scanning: Traverse the sorted events from the beginning, updating the current simultaneous usage count current_overlap as we go.
   • If there are multiple events at the same time, process all of them before checking for the maximum value.
   • The maximum value of current_overlap recorded during the scan is the answer.

Complexity

• Time complexity: \(O(N \log N)\)
  • Creating the events takes \(O(N)\).
  • Sorting the \(2N\) events takes \(O(N \log N)\).
  • Scanning the events after sorting takes \(O(N)\).
  • Overall, sorting is the dominant factor, giving \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the list storing the \(2N\) events.

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python, using sys.stdin.read().split() or similar methods to read all input at once can reduce execution time.

• Handling events at the same time: When a “start” and “end” occur at the same time, the problem’s conditions (start time is inclusive, end time is exclusive) must be correctly reflected. In our code, all events at the same time are accumulated using a while loop before updating the maximum, so the judgment is handled correctly.

  Source Code

import sys

def solve():
    # Read all input data at once and split into tokens for efficient processing.
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the number of meeting reservations.
    # T is the length of the day (not directly used in the calculation).
    N = int(input_data[0])
    
    # We use the "imoz" (difference array) method logic adapted for large T.
    # Each meeting from Si to Ei (exclusive) is an event.
    # At Si, the number of simultaneous meetings increases by 1.
    # At Ei, the number of simultaneous meetings decreases by 1.
    events = []
    for i in range(N):
        # S_i is at index 2 + 2*i, E_i is at index 3 + 2*i.
        s = int(input_data[2 + 2 * i])
        e = int(input_data[3 + 2 * i])
        events.append((s, 1))
        events.append((e, -1))
    
    # Sort the events by time. Python's Timsort is O(M log M) where M is the number of events.
    # Sorting ensures we process the timeline chronologically.
    events.sort()
    
    max_overlap = 0
    current_overlap = 0
    
    n_events = len(events)
    i = 0
    # Iterate through the sorted events to find the maximum simultaneous count.
    while i < n_events:
        current_time = events[i][0]
        # Process all events that occur at the same timestamp together.
        # This provides the net number of active meetings for the interval starting at this time.
        while i < n_events and events[i][0] == current_time:
            current_overlap += events[i][1]
            i += 1
        
        # Update the maximum simultaneous count observed across all time intervals.
        if current_overlap > max_overlap:
            max_overlap = current_overlap
            
    # Output the result.
    print(max_overlap)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.