概要

\(N\) 個の会議の開始時刻 \(S_i\) と終了時刻 \(E_i\) が与えられたとき、どの瞬間において最も多くの会議が重なっているか（最大同時利用数）を求める問題です。

考察

この問題で最も注意すべき点は、時間の範囲 \(T\) が最大で \(10^9\) と非常に大きいことです。

もし \(T\) が小さければ、時刻 \(0\) から \(T\) までの配列を用意して「いもす法」を適用できますが、 \(T = 10^9\) ではメモリ不足や時間切れ（TLE）になってしまいます。そこで、「同時利用数が変化するのは、会議が始まる瞬間か終わる瞬間だけである」という性質を利用します。

各会議の開始と終了を「イベント」として捉え、イベントが発生する時刻のみに注目して処理を行うことで、 \(T\) の大きさに依存せずに計算することが可能になります。

アルゴリズム

イベントソートと呼ばれる手法を用いて解きます。

1. イベントのリスト作成: 各予約について、以下の2つのイベントを作成し、1つのリストに格納します。
   • 時刻 \(S_i\) に会議が1つ増える： (S_i, 1)
   • 時刻 \(E_i\) に会議が1つ減る： (E_i, -1)
2. ソート: 作成した全 \(2N\) 個のイベントを、時刻の昇順（早い順）に並べ替えます。
3. 走査（スキャン）: ソートされたイベントを先頭から順に見ていき、現在の同時利用数 current_overlap を更新していきます。
   • 同じ時刻に複数のイベントがある場合は、それらをすべて処理した後に最大値の判定を行います。
   • 走査の中で current_overlap が記録した最大値が、求める答えとなります。

計算量

• 時間計算量: \(O(N \log N)\)
  • イベントの作成に \(O(N)\) かかります。
  • \(2N\) 個のイベントのソートに \(O(N \log N)\) かかります。
  • ソート後のイベントの走査は \(O(N)\) です。
  • 全体としてソートが支配的となり、 \(O(N \log N)\) となります。
• 空間計算量: \(O(N)\)
  • \(2N\) 個のイベントを保存するためのリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 同時刻の処理: 同じ時刻に「開始」と「終了」が重なる場合、問題文の条件（開始時刻は含み、終了時刻は含まない）を正しく反映させる必要があります。今回のコードでは、同じ時刻のイベントを while ループですべて合算してから最大値を更新しているため、正しく判定できています。

  ソースコード

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()

この解説は gemini-3-flash-preview によって生成されました。