LeetCode 题解工作台
你可以工作的最大周数
给你 n 个项目，编号从 0 到 n - 1 。同时给你一个整数数组 milestones ，其中每个 milestones[i] 表示第 i 个项目中的阶段任务数量。 你可以按下面两个规则参与项目中的工作： 每周，你将会完成 某一个 项目中的 恰好一个 阶段任务。你每周都 必须 工作。 在 连续的…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们考虑什么情况下不能完成所有阶段任务。如果存在一个项目 ，它的阶段任务数大于其余所有项目的阶段任务数之和再加 ，那么就不能完成所有阶段任务。否则，我们一定可以通过不同项目之间来回穿插的方式完成所有阶段任务。 我们记所有项目的阶段任务数之和为 ，最大的阶段任务数为 ，那么其余所有项目的阶段任务数之和为 $rest = s - mx$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你 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.length1 <= n <= 1051 <= milestones[i] <= 109
解题思路
方法一：贪心
我们考虑什么情况下不能完成所有阶段任务。如果存在一个项目 ，它的阶段任务数大于其余所有项目的阶段任务数之和再加 ，那么就不能完成所有阶段任务。否则，我们一定可以通过不同项目之间来回穿插的方式完成所有阶段任务。
我们记所有项目的阶段任务数之和为 ，最大的阶段任务数为 ，那么其余所有项目的阶段任务数之和为 。
如果 ，那么就不能完成所有阶段任务，最多只能完成 个阶段任务。否则，我们可以完成所有阶段任务，数量为 。
时间复杂度 ，其中 为项目数。空间复杂度 。
class Solution:
def numberOfWeeks(self, milestones: List[int]) -> int:
mx, s = max(milestones), sum(milestones)
rest = s - mx
return rest * 2 + 1 if mx > rest + 1 else s
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate should be comfortable with greedy algorithms and invariant management.
- question_mark
Look for efficiency in selecting and updating projects based on remaining milestones.
- question_mark
Candidates who suggest using a heap or priority queue demonstrate an understanding of efficient tracking.
常见陷阱
外企场景- error
Failing to properly manage the condition of not working on the same project consecutively.
- error
Not using efficient data structures, leading to slower performance as project numbers grow.
- error
Overlooking edge cases where some projects may have fewer milestones than others.
进阶变体
外企场景- arrow_right_alt
What happens if the milestone values are extremely large (close to 10^9)?
- arrow_right_alt
What if projects have the same number of milestones?
- arrow_right_alt
How would the approach change if we were asked to minimize the number of weeks instead of maximizing them?