概要

各会議を「開始で +1、終了で -1」のイベントとして扱い、時刻順に重なり数を数えながら、同時開催数が \(K\) 以上になる瞬間があるかを判定します。

考察

会議 \(i\) は区間 \([S_i, E_i)\)（開始は含む、終了は含まない）で行われます。したがって「ある時刻に同時に何件行われているか」は、時間の流れに沿って 開始で増え、終了で減る という形で管理できます。

素朴に各時刻を調べようとしても、時刻は最大 \(10^9\) まであり、全時刻を走査することは不可能です。また、全会議ペアの重なりを調べるような方法は \(O(N^2)\) になり、\(N \le 2\times 10^5\) では間に合いません。

そこで、会議の開始・終了だけに注目します。重なり数が変化するのは開始時刻か終了時刻の瞬間だけなので、それらを並べ替えて順に処理すれば十分です。

特に注意が必要なのが 同じ時刻に終了と開始がある場合 です。区間が \([S, E)\) なので、例えば時刻 \(t\) で「ある会議が終了し、別の会議が開始」する場合、時刻 \(t\) では終了した会議はもう数えず、開始した会議は数えます。
つまり同時刻では 終了（-1）を先に処理してから開始（+1） を処理する必要があります。

アルゴリズム

1. 各会議 \((S_i, E_i)\) について、次の 2 つのイベントを作る。
   • 開始イベント: \((S_i, +1)\)
   • 終了イベント: \((E_i, -1)\)
2. 全イベントを「時刻の昇順」でソートする。時刻が同じなら 終了(-1) → 開始(+1) の順になるように並べる。
3. cur を現在の同時開催数として 0 から始め、イベントを順に処理する。
   • イベントの増減 d を cur += d で反映
   • cur >= K になったら、その瞬間が存在するので Yes を出力して終了
4. 最後まで到達したら No を出力

（具体例）
会議が \([1,3)\) と \([3,5)\) のとき、時刻 3 では前者は終了しており後者は開始しているので重なりは 1 件です。
イベントは \((1,+1),(3,-1),(3,+1),(5,-1)\) となり、時刻 3 では -1 を先に処理することで重なりを正しく数えられます。

計算量

• 時間計算量: \(O(N \log N)\)（イベント \(2N\) 個のソート）
• 空間計算量: \(O(N)\)（イベント配列）

実装のポイント

• ソートのキーを (時刻, 増減) とし、-1 の方が +1 より先に来るようにする（Pythonでは -1 < +1 なのでそのままでよい）。

• 入力が大きいので sys.stdin.buffer.read() を使うと高速に読み込めます。

• cur >= K になった時点で即終了すると無駄がありません。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    K = int(next(it))

    events = []
    for _ in range(N):
        s = int(next(it)); e = int(next(it))
        events.append((s, 1))   # start
        events.append((e, -1))  # end

    events.sort(key=lambda x: (x[0], x[1]))  # end(-1) before start(+1) at same time

    cur = 0
    for _, d in events:
        cur += d
        if cur >= K:
            sys.stdout.write("Yes\n")
            return
    sys.stdout.write("No\n")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。