Pythonでコースの開始・終了時刻から受講できる最大コース数を求める方法

この記事では、コースの開始時刻と終了時刻を表す区間リスト [start, end] が与えられたときに、受講できるコースの最大数を求めるPythonプログラムを解説します。条件として、同時に受講できるのは1つのコースのみで、次のコースの開始時刻は直前に受講したコースの終了時刻より後である必要があります。

例えば、入力が times = [[3, 6], [6, 9], [7, 8], [9, 11]] の場合、出力は 3 となります。これは [3, 6]、[7, 8]、[9, 11] の3つのコースを受講できるためです。

解決の手順

この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。手順は以下の通りです。

1. コースを終了時刻の早い順にソートする
2. カウンター counter を 0、変数 end を -1 で初期化する
3. times の各要素について以下を繰り返す：
   • そのコースの開始時刻 times[i][0] が end より大きい場合、counter を1増やし、end をそのコースの終了時刻 times[i][1] に更新する
4. 最後に counter を返す

なぜこのアルゴリズムが有効か

終了時刻の早い順にソートしておくことで、各ステップで「現時点で選べる中で最も早く終わるコース」を常に選択できます。これにより、後続のコースの選択肢を最大限に残せるため、結果として受講できるコース総数が最大になります。

計算量については、ソートに O(n log n)、走査に O(n) が必要となるため、全体の時間計算量は O(n log n) です。

実装例

class Solution:
   def solve(self, times):
      times.sort(key=lambda x: x[1])

      counter = 0
      end = -1

      for i in range(len(times)):
         if times[i][0] > end:
            counter += 1
            end = times[i][1]
      return counter

ob = Solution()
times = [
   [3, 6],
   [6, 9],
   [7, 8],
   [9, 11]
]
print(ob.solve(times))

入力

[[3, 6], [6, 9], [7, 8], [9, 11]]

出力

3

このように、終了時刻でソートして先頭から貪欲に選んでいくシンプルなアプローチで、区間スケジューリング問題を短いコードで解決できます。面接や競技プログラミングでも頻出のパターンなので、ぜひ覚えておきましょう。