概要

\(N\) 件の会議の時間帯が与えられたとき、同時に \(K\) 件以上の会議が重なる瞬間が存在するかを判定する問題です。「いもす法」（イベントソート）を用いて効率的に解くことができます。

考察

素朴なアプローチとその問題点

最も単純な方法は、すべての時刻について「その瞬間に何件の会議が行われているか」を数えることです。しかし、時刻の範囲が \(0\) から \(10^9\) まであるため、すべての時刻を調べると \(O(10^9)\) となり、到底間に合いません。

重要な気づき

同時開催数が変化するのは、会議が始まる瞬間と会議が終わる瞬間だけです。\(N\) 件の会議に対して、変化が起こるイベントは最大 \(2N\) 個しかありません。つまり、すべての時刻を調べる必要はなく、イベントが起こる時刻だけを調べれば十分です。

具体例

例えば、3件の会議 \([1, 5)\), \([2, 8)\), \([3, 6)\) があるとき、イベントを時系列で並べると：

\(K = 3\) なら、時刻 3 の時点で同時開催数が 3 に達するので Yes と判定します。

アルゴリズム

1. イベントの作成: 各会議 \(i\) について、開始時刻 \(S_i\) に \(+1\)（会議が1つ増える）、終了時刻 \(E_i\) に \(-1\)（会議が1つ減る）というイベントを作る。
2. イベントのソート: すべてのイベントを時刻の昇順にソートする。同じ時刻の場合、デフォルトのソートで \(-1\)（終了）が \(+1\)（開始）より先に処理される。これは、終了時刻 \(E_i\) は「\(E_i\) 未満」まで使用するため、時刻 \(E_i\) ちょうどでは既にその会議は終わっているという解釈に合致します。
3. 走査: イベントを順に処理しながら、現在の同時開催数 current を更新する。current が \(K\) 以上になった瞬間があれば Yes を出力して終了。
4. すべてのイベントを処理しても \(K\) 以上にならなければ No を出力。

計算量

• 時間計算量: \(O(N \log N)\)（イベントのソートがボトルネック）
• 空間計算量: \(O(N)\)（イベントリストの保持）

実装のポイント

• イベントのソート順: タプル \((時刻, 変化量)\) でソートすると、同じ時刻の場合に変化量 \(-1\)（終了）が \(+1\)（開始）より先に来ます。これは問題文の「時刻 \(S_i\) 以上 \(E_i\) 未満」という半開区間の定義と整合しています。つまり、ある会議が時刻 \(t\) に終わり、別の会議が時刻 \(t\) に始まる場合、これらは「同時」とはみなされません。

• 高速入力: sys.stdin.buffer.read() を使うことで、大量の入力を高速に読み込んでいます。\(N\) が最大 \(2 \times 10^5\) のため、通常の input() を繰り返すより効率的です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    events = []
    for i in range(N):
        S = int(input_data[idx]); idx += 1
        E = int(input_data[idx]); idx += 1
        events.append((S, 1))
        events.append((E, -1))
    
    events.sort()
    
    current = 0
    for time, delta in events:
        current += delta
        if current >= K:
            print("Yes")
            return
    
    print("No")

main()

この解説は claude4.6opus-thinking によって生成されました。