[LeetCode] 1953. Maximum Number of Weeks for Which You Can Work

There are n projects numbered from 0 to n - 1. You are given an integer array milestones where each milestones[i] denotes the number of milestones the ith project has.

You can work on the projects following these two rules:
Every week, you will finish exactly one milestone of one project. You must work every week.
You cannot work on two milestones from the same project for two consecutive weeks.

Once all the milestones of all the projects are finished, or if the only milestones that you can work on will cause you to violate the above rules, you will stop working. Note that you may not be able to finish every project’s milestones due to these constraints.

Return the maximum number of weeks you would be able to work on the projects without violating the rules mentioned above.

Example 1:
Input: milestones = [1,2,3]
Output: 6
Explanation: One possible scenario is:
​​​​- During the 1st week, you will work on a milestone of project 0.

• During the 2nd week, you will work on a milestone of project 2.
• During the 3rd week, you will work on a milestone of project 1.
• During the 4th week, you will work on a milestone of project 2.
• During the 5th week, you will work on a milestone of project 1.
• During the 6th week, you will work on a milestone of project 2.
  The total number of weeks is 6.

Example 2:
Input: milestones = [5,2,1]
Output: 7
Explanation: One possible scenario is:

• During the 1st week, you will work on a milestone of project 0.
• During the 2nd week, you will work on a milestone of project 1.
• During the 3rd week, you will work on a milestone of project 0.
• During the 4th week, you will work on a milestone of project 1.
• During the 5th week, you will work on a milestone of project 0.
• During the 6th week, you will work on a milestone of project 2.
• During the 7th week, you will work on a milestone of project 0.
  The total number of weeks is 7.
  Note that you cannot work on the last milestone of project 0 on 8th week because it would violate the rules.
  Thus, one milestone in project 0 will remain unfinished.

Constraints:
n == milestones.length
1 <= n <= 105
1 <= milestones[i] <= 109

你可以工作的最大周数。

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

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

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

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

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

思路

思路是贪心。题目要求我们尽可能多地完成任务且每两个连续的任务不能是同样的。为了尽可能多地完成任务，一个不难想到的思路是我们能否先找到任务量最多的任务，如果我们能完成这个任务量最多的任务，那么我们不就可以把剩下的任务穿插在这个最多的任务中间了吗？这样也满足题目不能连续两周做同一个任务的要求。

想到这个思路不难，这里我们说明一下这个思路的可行性。我们遍历一遍 input 数组，找到任务数量最多的任务，记为 longest。同时我们累加每一个任务，把全局所有任务数量的总和记为 sum，那么除 longest 之外的其他任务的数量 rest = sum - longest。假设我们能跑完 longest 的所有任务，那么我们至少需要 rest >= longest - 1。举例，比如 longest = 10，那么我们要让 rest 不小于 9 才行，因为 10 个任务中间有 9 个空隙可以插进去。

因此，当我们找到 longest 之后，我们可以直接判断，如果 rest >= longest - 1，那么可以完成所有任务；反之如果不满足这个条件，那么我们只能满足 2 * rest + 1 个任务。在剩下的 rest 个任务中间插入 rest + 1 个最多类型的任务。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public long numberOfWeeks(int[] milestones) {
        long longest = milestones[0];
		long sum = 0;
		for (int milestone : milestones) {
			longest = Math.max(longest, milestone);
			sum += milestone;
		}

		long rest = sum - longest;
		if (rest < longest - 1) {
			return rest * 2 + 1;
		}
		return sum;
    }
}