Python程式：求解完成部分作業可獲得的最大學分

假設我們有兩個大小相同的列表，分別表示截止日期和學分，它們代表課程作業。其中deadlines[i]表示作業i的截止日期，credits[i]表示作業i獲得的學分。我們每天只能完成一項作業，並且可以在截止日期之前或當天完成。我們不能同時完成多項作業。我們需要找到完成部分作業能夠獲得的最大學分。

例如，如果輸入為deadlines = [1, 2, 2, 2]，credits = [4, 5, 6, 7]，則輸出為18，因為我們可以在第0天完成學分為5的作業，在第1天完成學分為6的作業，在第2天完成學分為7的作業。

為了解決這個問題，我們將遵循以下步驟：

  • a：建立一個包含截止日期和學分的鍵值對，並根據學分降序排序。
  • 如果a為空，則
    • 返回0
  • res：建立一個大小為(1 + 最大截止日期)的列表，並用0填充。
  • ans := 0
  • 對於a中的每個鍵值對(i, j)，執行以下操作：
    • 對於k從i遞減到0，執行以下操作：
      • 如果res[k]為0，則
        • res[k] := 1
        • ans := ans + j
        • 退出迴圈
  • 返回ans

讓我們來看下面的實現，以便更好地理解：

示例

線上演示

class Solution:
   def solve(self, deadlines, credits):
      a = sorted(list(zip(deadlines, credits)), key=lambda x: x[1], reverse=True)
      if not a:
         return 0
      res = [0] * (max(deadlines) + 1)
      ans = 0
      for i, j in a:
         for k in range(i, -1, -1):
            if not res[k]:
               res[k] = 1
               ans += j
               break
      return ans
     
ob = Solution()
deadlines = [1, 2, 2, 2]
credits = [4, 5, 6, 7]
print(ob.solve(deadlines, credits))

輸入

[1, 2, 2, 2], [4, 5, 6, 7]

輸出

18

更新於：2020年12月2日

420 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.