Pythonで完了できるタスク数を求めるプログラムの書き方

問題の概要

タスクのリストと人のリストが与えられたとします。tasks[i] は i 番目のタスクを実行するために必要な体力（強さ）を表し、people[i] は i 番目の人が持っている体力を表します。ここで、「1人は最大でも1つのタスクしか担当できない」という条件のもとで、完了できるタスクの総数を求める必要があります。

例えば、入力が tasks = [4, 3, 9, 15]、people = [10, 5, 3, 2] の場合、出力は 3 になります。これは、1人目がタスク「9」を、2人目がタスク「4」を、3人目がタスク「3」をそれぞれ実行でき、4人目はどのタスクも実行できないためです。

解決のアプローチ

この問題は、両方のリストをあらかじめ昇順にソートしてから、貪欲法（グリーディ法）の要領で「最も弱い人から、まだ割り当てられていない最も軽いタスク」へ順にマッチングさせていくことで解けます。以下の手順に従います。

• リスト tasks を昇順にソートし、リスト people も昇順にソートする
• カウンター ct とインデックス ind をそれぞれ 0 で初期化する
• i を 0 から people のサイズまで繰り返す
  • j を ind から tasks のサイズまで繰り返す
    • people[i] >= tasks[j] であれば、ct を 1 増やし、ind を 1 増やして内側のループを抜ける
    • そうでなければ、その時点でループを抜ける
• 最後に ct を返す

このアルゴリズムでは、ソート済みのリストに対して各人が一度だけ走査されるため、計算量はソート部分が O(n log n)、マッチング部分が O(n + m) となり、非常に効率的です。

実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
   def solve(self, tasks, people):
      tasks.sort()
      people.sort()
      ct = 0
      ind = 0
      for i in range(len(people)):
         for j in range(ind, len(tasks)):
            if people[i] >= tasks[j]:
               ct += 1
               ind += 1
               break
            else:
               break
      return ct

ob = Solution()
tasks = [4, 3, 9, 15]
people = [10, 5, 3, 2]
print(ob.solve(tasks, people))

入力

[4, 3, 9, 15], [10, 5, 3, 2]

出力

3