你可以工作的最大周数

难度: Medium

给你 n 个项目，编号从 0 到 n - 1 。同时给你一个整数数组 milestones ，其中每个 milestones[i] 表示第 i 个项目中的阶段任务数量。

你可以按下面两个规则参与项目中的工作：

每周，你将会完成 某一个 项目中的 恰好一个 阶段任务。你每周都必须工作。
在 连续的 两周中，你不能参与并完成同一个项目中的两个阶段任务。

一旦所有项目中的全部阶段任务都完成，或者仅剩余一个阶段任务都会导致你违反上面的规则，那么你将 停止工作 。注意，由于这些条件的限制，你可能无法完成所有阶段任务。

返回在不违反上面规则的情况下你最多能工作多少周。

示例 1：

输入：milestones = [1,2,3]
输出：6
解释：一种可能的情形是：
- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 2 中的一个阶段任务。
- 第 3 周，你参与并完成项目 1 中的一个阶段任务。
- 第 4 周，你参与并完成项目 2 中的一个阶段任务。
- 第 5 周，你参与并完成项目 1 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
总周数是 6 。

示例 2：

输入：milestones = [5,2,1]
输出：7
解释：一种可能的情形是：
- 第 1 周，你参与并完成项目 0 中的一个阶段任务。
- 第 2 周，你参与并完成项目 1 中的一个阶段任务。
- 第 3 周，你参与并完成项目 0 中的一个阶段任务。
- 第 4 周，你参与并完成项目 1 中的一个阶段任务。
- 第 5 周，你参与并完成项目 0 中的一个阶段任务。
- 第 6 周，你参与并完成项目 2 中的一个阶段任务。
- 第 7 周，你参与并完成项目 0 中的一个阶段任务。
总周数是 7 。
注意，你不能在第 8 周参与完成项目 0 中的最后一个阶段任务，因为这会违反规则。
因此，项目 0 中会有一个阶段任务维持未完成状态。

提示：

n == milestones.length
1 <= n <= 10⁵
1 <= milestones[i] <= 10⁹

Submission

运行时间: 42 ms

内存: 26.7 MB

class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        mx = max(milestones)
        sm = sum(milestones) - mx
        if mx <= sm +1:
            return mx + sm
        else:
            return 2* sm + 1

Explain

这个问题的解决方案是通过比较最大的项目里的任务数（mx）与其他所有项目的任务总数（sm）来决定。主要思路是：如果最大项目的任务数不超过其他项目总任务数加1，那么可以在不违反规则的情况下完成总任务数（mx + sm）。否则，你将被迫在最大项目中连续工作，违反规则。在这种情况下，你能工作的最大周数是其他所有项目的两倍任务数（因为每个任务可以与最大项目的任务交替进行），再加上1（最初的一周可以从最大项目开始）。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        mx = max(milestones)  # 找到任务数最多的项目的任务数量
        sm = sum(milestones) - mx  # 计算除了任务数最多的项目外的所有任务的总数
        if mx <= sm + 1:
            return mx + sm  # 如果最大项目的任务数不超过其他所有项目的任务数总和+1，可以完成所有任务
        else:
            return 2 * sm + 1  # 否则，最多可以工作的周数为2*sm+1

Explore

为了确保不违反连续两周不能完成同一个项目的任务的规则，算法需要在选择任务时进行交替。具体来说，每次选择当前可用任务数最多的项目进行工作，然后再选择下一个任务数最多的不同项目。这样，只要条件`mx <= sm + 1`成立，即最大单一项目的任务数不超过其他所有项目任务总和加1，就可以保证每周都能选择不同的项目来工作，从而遵守规则。如果条件不成立，则需要特别安排，确保在达到最大周数时仍然保持交替进行不同项目的任务。

条件`mx <= sm + 1`意味着最大单项目的任务数不超过其他所有项目的任务总和加1。这保证了即使最大项目的任务数最多，也总有足够的其他项目的任务可以用来交替执行，从而避免连续两周完成同一个项目的任务。因此，可以安全地执行所有任务（即总任务数mx + sm），而不违反规则。

当`mx > sm + 1`时，意味着最大项目的任务数量超过了其他所有项目的任务总和加1。这种情况下，即使尽最大努力交替执行任务，最大项目的任务数依然过多，无法完全用其他项目的任务进行平衡。因此，我们能交替执行的最大周数是每个非最大项目任务交替一次，总共`2 * sm`（每个任务可以与最大项目的任务交替一次），加上第一周直接从最大项目开始的一周，总共是`2 * sm + 1`。

这种算法假设输入的任务数都是非负整数，并且理论上支持任何大小的数组。由于使用了`max`和`sum`函数，算法的时间复杂度主要由这两个操作决定，对于非常大的数组，这些操作的时间成本将会增加。如果数组中包含特殊值如负数，则算法的前提（任务数为非负）被违反，可能导致不正确的结果。因此，算法适用于任务数为非负整数的正常输入情况。