发表于 2024.05.16

• 这种任务规划题基本可以考虑利用贪心解决，通过观察发现，可以完成所有工作的充要条件为max_ <= rest + 1，其中mex_为耗时最长的工作量，而rest则为其他的工作量。最优的安排即为将分配工作时间的过程转化为在[1,longest+rest]闭区间内分配整数的过程，其中每个整数代表对应的一周时间。在分配整数的过程中，首先按照从小到大的顺序分配所有的奇数，然后按照从小到大的顺序分配所有的偶数，这样就可以避免各个数的重复相邻！详细证明可以见官解。

  class Solution:
      def numberOfWeeks(self, milestones: List[int]) -> int:
          # 贪心 + 数学
          # 能消耗最多的可能做法: 取max一次 -> 取其他一次 -> 取max一次 -> ...
          sum_ = sum(milestones)
          max_ = max(milestones)
          rest = sum_ - max_
          return sum_ if rest + 1 >= max_ else (sum_ - (max_ - rest) + 1)

• LC 题目链接