JZX轻语：简

LeetCode 1953 - 你可以工作的最大周数

发表于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

题目链接：https://leetcode.cn/problems/maximum-number-of-weeks-for-which-you-can-work/