概要

\(N\) 個の会議のスケジュール（開始時刻 \(S_i\)、終了時刻 \(E_i\)）が与えられたとき、同時に \(K\) 個以上の会議が行われている瞬間があるかどうかを判定する問題です。会議は \([S_i, E_i)\) の半開区間として定義されており、終了時刻 \(E_i\)ちょうどには会議は終了しているものとして扱います。

考察

1. 素朴なアプローチの限界

まず、時刻が \(0 \leq S_i < E_i \leq 10^9\) と非常に広いため、各時刻（1秒ごとなど）について会議の数を数えることは不可能です。 また、全ての会議のペア（約 \(N^2\) 通り）を比較して重なりを調べる方法も、 \(N = 2 \times 10^5\) という制約下では計算時間がかかりすぎてしまい（\(O(N^2)\)）、制限時間内に終わりません。

2. 重要な気づき

「同時に行われている会議の数」が変化するのは、どこかの会議が始まる瞬間 (\(S_i\)) か、終わる瞬間 (\(E_i\)) だけです。 それ以外の時刻では、会議の数は一定です。したがって、すべての会議の開始・終了時刻だけを抜き出して、時系列順に調べていけば効率的に解けそうです。

3. 半開区間の扱い

問題文に「時刻 \(S_i\) 以上 \(E_i\) 未満」とあるため、時刻 \(E_i\) に別の会議 \(j\) が開始する場合（\(E_i = S_j\)）、それらは「同時」とはみなされません。 イベントを処理する際、同じ時刻に「開始」と「終了」が重なった場合は、「終了」を先に処理することで、同時開催数を正しくカウントできます。

アルゴリズム

イベントソート（スイープライン法）

この問題は、イベントソートと呼ばれる手法で効率よく解くことができます。

1. イベントの作成: 各会議について、以下の2つのイベントを作成します。
   • 時刻 \(S_i\) に会議が1つ増える（\(+1\)）
   • 時刻 \(E_i\) に会議が1つ減る（\(-1\)）
2. ソート: 作成した \(2N\) 個のイベントを時刻の昇順でソートします。
   • 時刻が同じ場合は、終了イベント（\(-1\)）を開始イベント（\(+1\)）より先に並べるようにします。
3. 走査（スイープ）: ソートされたイベントを先頭から順に見ていき、現在の会議数 current_count を更新していきます。
   • current_count が一度でも \(K\) 以上になれば、Yes を出力して終了します。
   • すべてのイベントを処理しても \(K\) 以上にならなければ、No を出力します。

計算量

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

実装のポイント

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

• ソートの工夫: Pythonのタプルをソートする場合、第1要素が同じなら第2要素で比較されます。イベントを (時刻, 増減値) の形で持ち、終了を -1、開始を 1 とすることで、同じ時刻なら -1（終了）が先に処理されるようになり、問題の条件（半開区間）を自然に満たすことができます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # これにより、大量の入力データを効率的に処理できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 会議の件数 N と同時開催の上限 K を取得します。
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 各会議の開始時刻と終了時刻をイベントとしてリストに格納します。
    # 会議は [Si, Ei) の半開区間であるため、時刻 Ei では会議は終了しています。
    # スイープライン法（平面走査法）を用いて、同時に開催されている会議の数をカウントします。
    events = []
    for i in range(N):
        s = int(input_data[2 + 2*i])
        e = int(input_data[3 + 2*i])
        
        # 開始イベントを +1、終了イベントを -1 とします。
        # Pythonのタプルのソート順序を利用し、同じ時刻にイベントが重なった場合、
        # 終了イベント (-1) が開始イベント (1) よりも先に処理されるようにします。
        # これにより、時刻 Ei に別の会議が開始する場合でも、正しくカウントできます。
        events.append((s, 1))
        events.append((e, -1))
    
    # イベントを時刻順にソートします。時刻が同じ場合は、第2要素の -1 が 1 より先に来ます。
    events.sort()
    
    current_count = 0
    # 各イベントを順番に処理し、現在の会議数を更新していきます。
    for _, etype in events:
        current_count += etype
        
        # 同時に開催されている会議の数が K 以上になった瞬間があれば、Yes を出力して終了します。
        if current_count >= K:
            print("Yes")
            return
            
    # すべてのイベントを処理しても K 以上にならなければ、No を出力します。
    print("No")

if __name__ == '__main__':
    main()

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