Pythonですべての映画を上映するために必要な映画館の最小数を求めるプログラム

複数の映画の上映時間を表す区間のリストが与えられます(区間同士は重なる場合があります)。このとき、すべての映画を上映するために最低限必要な映画館の数を求める問題を考えてみましょう。

例えば、入力が intervals = [[20, 65], [0, 40], [50, 140]] の場合、出力は 2 になります。これは、[20, 65] と [0, 40] が重なっており、[20, 65] と [50, 140] も重なっていますが、[0, 40] と [50, 140] は重なっていないためです。つまり、同時に上映されている映画の最大本数が2本なので、2つのスクリーン(映画館)があれば十分だということです。

解決のアプローチ

この問題は、イベントソートと累積和を組み合わせたテクニック(いもす法として知られる手法)を使うと効率的に解けます。考え方はシンプルで、各区間の開始時刻でカウントを+1、終了時刻で-1します。その後、時刻順に並べ替えてカウントの累積値を追跡することで、各時点で同時に上映されている映画の本数がわかり、その最大値が求める答えになります。

アルゴリズムの手順

• 新しいリスト t を作成します。
• intervals 内の各区間 [a, b] について、次の処理を行います。
  • t の末尾に (a, 1)(開始イベント)を追加します。
  • t の末尾に (b, -1)(終了イベント)を追加します。
• ans = 0、count = 0 で初期化します。
• ソート後の t 内の各ペア (x, d) について、次の処理を行います。
  • count に d を加算します。
  • ans を ans と count の最大値で更新します。
• 最後に ans を返します。

実装コード

それでは、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, intervals):
        t = []
        for a, b in intervals:
            t.append((a, 1))
            t.append((b, -1))
        ans = count = 0
        for x, d in sorted(t):
            count += d
            ans = max(ans, count)
        return ans

ob = Solution()
intervals = [[20, 65], [0, 40], [50, 140]]
print(ob.solve(intervals))

入力

[[20, 65], [0, 40], [50, 140]]

出力

2

補足ポイント

• 計算量: 区間の数を n とすると、イベントのソートが支配的になるため、時間計算量は O(n log n)、空間計算量は O(n) となります。
• 境界の扱い: Pythonのタプル比較により、同じ時刻では (時刻, -1) の終了イベントが (時刻, 1) の開始イベントより先に処理されます。そのため、「ある映画の終了時刻 = 別の映画の開始時刻」の場合は重複とみなされず、同じスクリーンを再利用できる扱いになります。
• 応用範囲: この手法は会議室の割り当てやタスクスケジューリングなど、「区間の最大同時重複数」を求めるあらゆる問題に応用できます。