概要

会議の開始時刻と終了時刻が与えられたとき、同時にK件以上の会議が行われている瞬間があるかどうかを判定する問題です。

考察

各会議の区間 \([S_i, E_i)\) について、どの時刻で何件の会議が同時に行われているかを調べる必要があります。素朴なアプローチでは、すべての時刻を調べることは \(E_i\) の最大値が \(10^9\) にもなるため、現実的ではありません。代わりに、会議の開始時刻と終了時刻だけに注目して、イベントポイント（開始と終了）を時系列順に処理することで、効率的に重なり数を計算できます。

アルゴリズム

イベントベースのスイープライン法を使用します。各会議について、開始時刻に「+1」、終了時刻に「-1」のイベントを作成します。これらのイベントを時刻の昇順にソートし、同じ時刻の場合は終了イベント（-1）を先に処理します（これにより、同じ時刻で会議が終了してから開始されるため、正しく重なり数を数えられます）。ソートされたイベントを順に処理しながら、現在の重なり数を計算し、一度でもK以上になった時点で「Yes」を出力します。すべてのイベントを処理してもK以上にならなければ「No」を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • イベントの数は \(2N\) 個で、ソートに \(O(N \log N)\) かかります。スイープ処理は \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • イベントを格納するための配列のサイズが \(2N\) です。

実装のポイント

• イベントは（時刻, 種類）のタプルで表現し、種類は開始を+1、終了を-1とします。

• ソート時には、同じ時刻の場合に終了イベント（-1）を先に処理するようにします。これにより、ある時刻で会議が終了してから新しい会議が開始されるため、重なり数を正しく計算できます。

• 現在の重なり数を保持する変数を更新しながら、K以上になった時点で即座に「Yes」を出力して終了します。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print("No")
        return
        
    n = int(data[0])
    k = int(data[1])
    events = []
    index = 2
    
    for i in range(n):
        s = int(data[index])
        e = int(data[index + 1])
        index += 2
        events.append((s, 1))
        events.append((e, -1))
    
    events.sort(key=lambda x: (x[0], x[1]))
    
    current = 0
    for time, typ in events:
        current += typ
        if current >= k:
            print("Yes")
            return
            
    print("No")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。