概要

会議の開始時刻と終了時刻のリストが与えられ、時間が重ならないように会議を最小数の会議室に割り当てる問題です。

考察

この問題は、区間スケジューリング問題の一種で、最小数の資源（会議室）ですべての区間（会議）をカバーする必要があります。重要な観察は、必要な会議室の最小数は、同時に進行している会議の最大数に等しいということです。つまり、どの時点でも最大で何個の会議が重なっているかを数えれば、それが最小の会議室数になります。

素朴なアプローチでは、すべての時点（例えば、各会議の開始時刻と終了時刻）について重なり数を計算すると、時間計算量が \(O(N^2)\) または \(O(N \times \text{時刻の範囲})\) となり、制約条件（\(N \leq 2 \times 10^5\)、時刻は \(10^9\) まで）では実行時間がかかりすぎます。

アルゴリズム

効率的な解法は、以下の手順で行います： 1. すべての会議を開始時刻 \(S_i\) でソートします。 2. 最小ヒープ（優先度付きキュー）を使用して、現在使用中の会議室の終了時刻を管理します。ヒープの先頭は最も早く終了する会議の時刻です。 3. 各会議について、現在の会議の開始時刻 \(S_i\) がヒープの先頭（最も早く終了する会議の時刻）以上ならば、その会議室を再利用できます。その場合、ヒープからその終了時刻を取り除き、新しい終了時刻 \(E_i\) を追加します。 4. そうでない場合は、新しい会議室が必要なので、新しい終了時刻 \(E_i\) をヒープに追加します。 5. 最終的にヒープのサイズが、必要な会議室の最小数になります。

この方法では、会議室の再利用を貪欲に行い、最小数の会議室で全ての会議をスケジュールできます。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)、各会議についてヒープ操作（push/pop）に \(O(\log N)\) かかるため、合計 \(O(N \log N)\) です。
• 空間計算量: \(O(N)\)
  • 会議のリストとヒープのサイズが最大 \(N\) まで成長するためです。

実装のポイント

• Pythonのheapqモジュールを使用して最小ヒープを実装します。ヒープの先頭が最小値であることを利用します。

• 会議を開始時刻でソートすることが重要です。これにより、会議を時系列順に処理できます。

• ヒープには各会議室の現在の終了時刻を保持します。新しい会議が開始するとき、最も早く終了する会議室が再利用できるかどうかをチェックします。

  ソースコード

import heapq

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    meetings = []
    index = 1
    for i in range(n):
        s = int(data[index])
        e = int(data[index + 1])
        index += 2
        meetings.append((s, e))
    
    meetings.sort(key=lambda x: x[0])
    
    rooms = []
    heapq.heappush(rooms, meetings[0][1])
    
    for i in range(1, n):
        s, e = meetings[i]
        earliest_end = rooms[0]
        if s >= earliest_end:
            heapq.heappop(rooms)
        heapq.heappush(rooms, e)
    
    print(len(rooms))

if __name__ == "__main__":
    main()

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