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 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告