概要

\(N\) 件の会議の開始時刻と終了時刻が与えられるので、ある瞬間に \(K\) 件以上の会議が同時に開催されるかどうかを判定する問題です。

考察

この問題の目的は、「任意の時間帯において、いくつの会議が同時に開催されているか」を効率的に求めることです。

素朴な方法（TLEになる理由）

例えば、各時刻ごとに何個の会議が行われているかを愚直に調べる方法があります。しかし、時刻の範囲が最大 \(10^9\) あり、会議数も最大 \(2 \times 10^5\) であるため、全ての時刻を調べるのは非現実的です。

また、会議の開始・終了時刻を一つずつ見ていくのも、区間が重なる組み合わせを毎回計算していると時間がかかりすぎます。

解決策：イベントソート（いもす法の変形）

重要なのは「会議が開始されるタイミング」と「会議が終了するタイミング」だけです。
それぞれの会議について、以下の2つのイベントを考えます： - 時刻 \(S_i\) に「会議が1つ増える」イベント - 時刻 \(E_i\) に「会議が1つ減る」イベント

これらのイベントを「時刻順にソート」して順番に処理することで、任意の瞬間における同時開催中の会議数を効率的にシミュレーションできます。

同じ時刻に開始と終了がある場合の処理

たとえば、ある会議Aが時刻 \(t\) に終了し、別の会議Bが時刻 \(t\) に開始される場合があります。このとき、「終了 → 開始」の順に処理することで、不必要なカウントを防ぎます。

たとえば以下のような順序で処理すると正しく動作します： - 同じ時刻なら、まず終了イベント（-1）を処理し、その後開始イベント（+1）を処理する

アルゴリズム

1. 各会議の開始時刻 \(S_i\) に対して「+1」イベント、終了時刻 \(E_i\) に対して「-1」イベントを作成します。
2. 全てのイベントを「時刻の昇順」にソートします。同じ時刻の場合は「-1（終了）を先に処理」するようにします。
3. ソートされたイベントを前から処理しながら、現在の会議数 current_meetings を更新します。
4. 最大の同時開催数 max_meetings を記録し、それが \(K\) 以上であれば Yes を出力します。

例

入力:

3 3
1 3
2 4
3 5

イベント列（時刻、増減）:

(1, +1), (2, +1), (3, -1), (3, +1), (4, -1), (5, -1)

ただし、同じ時刻では -1 を先に処理するので実際には：

(1, +1), (2, +1), (3, -1), (3, +1), (4, -1), (5, -1)

処理過程: - 時刻 1: +1 → 1件 - 時刻 2: +1 → 2件 - 時刻 3: -1 → 1件、その後 +1 → 2件（最大値は2） - 時刻 4: -1 → 1件 - 時刻 5: -1 → 0件

最大同時開催数は 2 なので、\(K=3\) の場合は No となります。

計算量

• 時間計算量: \(O(N \log N)\)
  　→ イベントのソートに dominate されます。
• 空間計算量: \(O(N)\)
  　→ イベントリストのサイズが \(2N\)

実装のポイント

• 開始時刻と終了時刻を別々のイベントとして扱う（いもす法的な発想）

• ソートキーを (time, delta) のように設定し、同じ時刻でも終了を先に処理するようにする

• sys.stdin.read を使うことで高速な入力処理を行う（\(N\) が大きいので重要）

  ソースコード

import sys
from collections import defaultdict

input = sys.stdin.read
data = input().split()

N = int(data[0])
K = int(data[1])

events = []

index = 2
for _ in range(N):
    s = int(data[index])
    e = int(data[index+1])
    index += 2
    events.append((s, 1))   # 開始イベント
    events.append((e, -1))  # 終了イベント

# イベントソート: 時刻で昇順、同じ時刻なら終了(-1)を先に処理
events.sort(key=lambda x: (x[0], x[1]))

current_meetings = 0
max_meetings = 0

for time, delta in events:
    current_meetings += delta
    max_meetings = max(max_meetings, current_meetings)

if max_meetings >= K:
    print("Yes")
else:
    print("No")

---

この解説は qwen3-coder-480b によって生成されました。