Pythonでシャッフルされた人々のキューを回復するプログラム

各行に2つの値[height、count]が含まれている2Dマトリックスがあるとします。これらは、人が身長を指定し、その前に少なくとも同じ高さの人が「count」人いることを示します。ここで、このキューがシャッフルされていると考えてください。キューの元の順序を復元する必要があります。

したがって、入力が次のような場合

その場合、出力は次のようになります

これを解決するには、次の手順に従います。

• N：=行列の行数
• 高さの増加とカウントの減少に基づいて行列の行を再配置します
• ans：=サイズNのリストを作成し、最初はすべてのエントリがnullです
• 高さhごとに、行列行のcを数えます。
  • temp：=0
  • 各インデックスi、および値num ansについて、実行します
    • temp> =cで、numがnullの場合、
      • ans [i]：=[h、c]
      • ループから抜け出す
    • numがnullまたはnum[0]>=hの場合、
      • temp：=temp + 1
• 回答を返す

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

例

class Solution:
   def solve(self, matrix):
      N = len(matrix)
      matrix.sort(key=lambda x: [x[0], -x[1]])
      ans = [None] * N

      for h, c in matrix:
         temp = 0
         for i, num in enumerate(ans):
            if temp >= c and num is None:
               ans[i] = [h, c]
               break

            if num is None or num[0] >= h:
               temp += 1
      return ans

ob = Solution()
matrix = [
   [2, 2],
   [4, 0],
   [5, 0]
]
print(ob.solve(matrix))

入力

[[2, 2],[4, 0],[5, 0]]

出力

[[4, 0], [5, 0], [2, 2]]