Pythonですべてのバス停を通過するために必要な最小のバス台数を求めるプログラム

問題の概要

「nums」という数値のリストがあるとします。これはある路線上のバス停を表しており、nums[i] はバスが i 番目の停留所に到着しなければならない時刻を示しています。バスは前方にしか進めないため、すべての停留所を通過するために必要な最小のバス台数を求める必要があります。

たとえば、入力が nums = [1, 2, 7, 9, 3, 4] の場合、出力は 2 になります。1 台目のバスが時刻順に [1, 2, 3, 4] の停留所を担当し、2 台目のバスが [7, 9] を担当できるからです。

解法のアプローチ

この問題は貪欲法（グリーディ法）を使って効率的に解くことができます。まだ訪れていない停留所を見つけるたびに新しいバスを割り当て、そのバスで到達可能な限り多くの停留所を時刻の昇順に通過させていきます。具体的な手順は以下の通りです。

• ans := 0（必要なバスの台数）

• seen := nums と同じ長さのリストで、初期値はすべて False（訪問済みかどうかのフラグ）

• 各インデックス i とその値 n について以下を繰り返します。

  • seen[i] が False の場合：

    • seen[i] := True とする

    • ans := ans + 1（新しいバスを1台追加）

    • prev := n（直前に通過した時刻を記録）

    • j を i+1 から nums の末尾まで繰り返します。

      • nums[j] > prev かつ seen[j] が False の場合：

        • seen[j] := True とする

        • prev := nums[j] と更新する

• 最後に ans を返します。

それでは、実際の実装を見て理解を深めましょう。

実装例

class Solution:
   def solve(self, nums):
      ans = 0
      seen = [False] * len(nums)
      for i, n in enumerate(nums):
         if not seen[i]:
            seen[i] = True
            ans += 1
            prev = n
            for j in range(i+1, len(nums)):
               if nums[j] > prev and not seen[j]:
                  seen[j] = True
                  prev = nums[j]
      return ans

ob = Solution()
nums = [1, 2, 7, 9, 3, 4]
print(ob.solve(nums))

入力

[1, 2, 7, 9, 3, 4]

出力

2

まとめ

このアルゴリズムでは、各停留所を一度ずつチェックするため、時間計算量は O(n²) となります。未訪問の停留所に出会うたびに新しいバスを起動し、そのバスが時刻の昇順で通過できる停留所をすべて割り当てることで、必要なバスの総台数を最小化できます。配列を「増加部分列」に分割する問題として捉えると、貪欲法の考え方がより直感的に理解できるでしょう。