Problem Description

You are given an array milestones where milestones[i] represents the number of tasks for the i-th project. Every week, you must work on exactly one task, and you can only work on one project each week. However, you cannot work on the same project in two consecutive weeks.

Your goal is to determine the maximum number of weeks you can work under these constraints, given that you must always pick a project with remaining tasks, and you cannot work on the same project two weeks in a row.

• Each task must be done in a separate week.
• You must never work on the same project in consecutive weeks.
• Return the maximum number of weeks you can work, given these rules.

Constraints:

• 1 <= milestones.length <= 10^5
• 1 <= milestones[i] <= 10^9

Thought Process

At first glance, you might try to simulate the process: alternate between projects, always picking one with remaining tasks, and avoid repeating the same project two weeks in a row. However, with large inputs, this brute-force simulation would be too slow.

Instead, let's reason about the constraints. The only rule is that you cannot pick the same project twice in a row. This means that if one project has a huge number of tasks compared to the others, eventually you'll be forced to break the rule because there are not enough other projects to alternate with.

The key insight is to look at the project with the most tasks. If the largest project has more tasks than the sum of all the others plus one, it will be impossible to alternate forever without repeating it. Otherwise, you can alternate freely between projects until all tasks are done.

Solution Approach

• Step 1: Calculate the total number of tasks: total = sum(milestones).
• Step 2: Find the project with the most tasks: max_tasks = max(milestones).
• Step 3: If max_tasks <= total - max_tasks + 1, you can work all weeks (i.e., finish all tasks) by alternating projects.
  • In this case, return total.
• Step 4: Otherwise, you are limited by the number of tasks in the other projects. You can alternate until the other projects run out, then you must stop to avoid working on the same project twice in a row.
  • The answer is 2 * (total - max_tasks) + 1 (alternate as much as possible, then do one extra task from the biggest project).

This approach is efficient because it only requires a single pass to find the sum and the maximum, and no simulation is needed.

Example Walkthrough

Example Input: milestones = [3, 2, 2]

• Total tasks: 3 + 2 + 2 = 7
• Max tasks in one project: 3
• Sum of other projects: 2 + 2 = 4
• Check: 3 <= 4 + 1 → 3 <= 5 (True)
• So, you can finish all 7 weeks.

Example Input 2: milestones = [7, 3, 2]

• Total tasks: 7 + 3 + 2 = 12
• Max tasks: 7
• Sum of others: 3 + 2 = 5
• Check: 7 <= 5 + 1 → 7 <= 6 (False)
• So, the answer is 2 * 5 + 1 = 11
• You alternate 5 times (using up all tasks from the smaller projects), then can do one more from the largest project.

Time and Space Complexity

• Brute-force approach: Would require simulating each week, which is O(N * max(milestones)) — not feasible for large inputs.
• Optimized approach: Only needs to compute the sum and the maximum, both of which can be done in a single pass (O(N) time, where N is the number of projects).
• Space complexity: O(1), since we only store a few variables regardless of input size.

Summary

The main insight is to recognize that the project with the most tasks can only be alternated as long as there are enough tasks in other projects. If not, you are limited by how many times you can alternate before being forced to repeat the same project. The solution is efficient, requiring only a single pass through the input, and elegantly handles all edge cases with a simple formula.

Code Implementation

class Solution:
    def numberOfWeeks(self, milestones):
        total = sum(milestones)
        max_tasks = max(milestones)
        if max_tasks <= total - max_tasks + 1:
            return total
        else:
            return 2 * (total - max_tasks) + 1
      

class Solution {
public:
    long long numberOfWeeks(vector<int>& milestones) {
        long long total = 0;
        int max_tasks = 0;
        for (int m : milestones) {
            total += m;
            max_tasks = max(max_tasks, m);
        }
        if (max_tasks <= total - max_tasks + 1)
            return total;
        else
            return 2 * (total - max_tasks) + 1;
    }
};
      

class Solution {
    public long numberOfWeeks(int[] milestones) {
        long total = 0;
        int max_tasks = 0;
        for (int m : milestones) {
            total += m;
            max_tasks = Math.max(max_tasks, m);
        }
        if (max_tasks <= total - max_tasks + 1)
            return total;
        else
            return 2 * (total - max_tasks) + 1;
    }
}
      

var numberOfWeeks = function(milestones) {
    let total = milestones.reduce((a, b) => a + b, 0);
    let max_tasks = Math.max(...milestones);
    if (max_tasks <= total - max_tasks + 1) {
        return total;
    } else {
        return 2 * (total - max_tasks) + 1;
    }
};