# Maximum Number of Weeks for Which You Can Work
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-weeks-for-which-you-can-work)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-weeks-for-which-you-can-work
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [SAP](https://scaleengineer.com/companies/sap), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo)
---
## Problem
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`

# Approaches
## Greedy Approach with Sorting
The core idea of this approach is to identify the project with the most milestones, as it is the most constrained and dictates the scheduling limits. By sorting the array, we can easily find this maximum value. We then compare this maximum count against the sum of all other milestones to determine if it's possible to complete all projects or if the dominant project will leave unfinished work.
**Time:** O(N log N) · **Space:** O(log N) or O(N)
**Pros:** The logic is correct and covers all cases.; It's relatively straightforward to implement once the core greedy insight is understood.
**Cons:** The `O(N log N)` time complexity from sorting is not optimal.; Sorting the entire array is unnecessary, as we only need the maximum element and the total sum.
### Explanation
This approach relies on a crucial insight about the problem's constraint. The rule that you cannot work on the same project for two consecutive weeks implies that the number of tasks from any single project cannot be more than one greater than the number of tasks from all other projects combined in a valid schedule. 

By sorting the `milestones` array, we can find the project with the maximum number of milestones, `max_m`, in `O(N log N)` time. We then calculate `rest_sum`, the sum of all other milestones. 

If `max_m` is less than or equal to `rest_sum + 1`, the largest project is not 'too large'. We can always construct a schedule to finish all milestones, for example, by always picking a task from the currently largest pile, which is not the same as the previous week's pile. The total work will be the sum of all milestones. 

However, if `max_m` is greater than `rest_sum + 1`, the largest project is a bottleneck. We can schedule `rest_sum` tasks from the largest project, each followed by a task from another project. This gives `2 * rest_sum` weeks. After this, all other projects are exhausted. We can work one final week on the largest project. This gives a total of `2 * rest_sum + 1` weeks.

```java
import java.util.Arrays;

class Solution {
    public long maximumNumberOfWeeks(int[] milestones) {
        int n = milestones.length;
        // A single project can be worked on for 1 week.
        if (n == 1) {
            return 1;
        }

        // Sort the array to easily find the max milestone
        Arrays.sort(milestones);

        // The last element is the max
        long maxM = milestones[n - 1];
        long restSum = 0;
        for (int i = 0; i < n - 1; i++) {
            restSum += milestones[i];
        }

        // Check if the max project is a bottleneck
        if (maxM > restSum + 1) {
            // We are limited by the number of other projects' milestones
            return 2 * restSum + 1;
        } else {
            // We can complete all milestones
            return restSum + maxM;
        }
    }
}
```
### Algorithm
- Sort the `milestones` array in non-decreasing order.
- The largest milestone count, `max_m`, will be the last element of the sorted array.
- Calculate the sum of all other milestones, `rest_sum`, by summing up the first `n-1` elements.
- The total number of milestones is `total_sum = rest_sum + max_m`.
- **Case 1: The dominant project is not a bottleneck.** If `max_m <= rest_sum + 1`, it means we can always interleave the tasks from the largest project with tasks from other projects. Thus, all milestones can be completed. The total number of weeks is `total_sum`.
- **Case 2: The dominant project is a bottleneck.** If `max_m > rest_sum + 1`, we cannot complete all milestones of the largest project. We can use all `rest_sum` milestones to pair with milestones from the largest project, accounting for `2 * rest_sum` weeks. After that, only the largest project has milestones left. We can work for one more week on it. The total number of weeks is `2 * rest_sum + 1`.
- Return the result based on the condition.

## Greedy Approach with Linear Scan
This approach is an optimization of the sorting-based method. It recognizes that we don't need the full sorted order of the milestones. All we need is the single largest milestone count and the total sum of all milestones. Both of these can be computed efficiently in a single pass through the input array, leading to a linear time solution.
**Time:** O(N) · **Space:** O(1)
**Pros:** Achieves optimal time complexity of O(N).; Requires only O(1) extra space.; Simple and concise to implement.
**Cons:** The mathematical reasoning behind the formula might not be immediately obvious.
### Explanation
The fundamental logic of this approach is identical to the sorting approach, based on the relationship between the largest project (`max_m`) and the sum of all other projects (`rest_sum`). The key difference is in the implementation efficiency. Instead of sorting the array to find the maximum element, we can find both the maximum element and the total sum in a single linear scan.

We iterate through the `milestones` array, keeping track of the running total sum and the maximum value encountered. This gives us `total_sum` and `max_m` in `O(N)` time. From these, we derive `rest_sum = total_sum - max_m`. The final calculation remains the same: if the largest project is too dominant (`max_m > rest_sum + 1`), the result is `2 * rest_sum + 1`. Otherwise, all milestones can be completed, and the result is `total_sum`. This method avoids the `O(N log N)` sorting overhead, making it the most efficient solution.

```java
class Solution {
    public long maximumNumberOfWeeks(int[] milestones) {
        // Use long for sums to avoid overflow, as milestones[i] can be large
        // and n can be up to 10^5.
        long totalSum = 0;
        long maxM = 0;

        for (int m : milestones) {
            totalSum += m;
            if (m > maxM) {
                maxM = m;
            }
        }

        // The sum of all other milestones
        long restSum = totalSum - maxM;

        // If the largest project has more milestones than all others combined + 1,
        // it becomes the bottleneck for scheduling.
        if (maxM > restSum + 1) {
            // In this case, we can use all milestones from other projects, pairing each 
            // with one from the max project. This gives 2 * restSum weeks.
            // Then, we can work one final week on the max project before getting stuck.
            return 2 * restSum + 1;
        } else {
            // The max project is not a bottleneck. We can complete all milestones
            // by carefully interleaving projects.
            return totalSum;
        }
    }
}
```
### Algorithm
- Initialize two variables: `total_sum = 0` and `max_m = 0`.
- Iterate through the `milestones` array once.
- In each iteration, add the current milestone count to `total_sum`.
- Also, update `max_m` to be the maximum value seen so far: `max_m = max(max_m, current_milestone)`.
- After the loop, calculate the sum of all other milestones: `rest_sum = total_sum - max_m`.
- Apply the same logic as the sorting approach: if `max_m > rest_sum + 1`, return `2 * rest_sum + 1`. Otherwise, return `total_sum`.

# Solutions
### Java

```java
class Solution {
public
  long numberOfWeeks(int[] milestones) {
    int mx = 0;
    long s = 0;
    for (int e : milestones) {
      s += e;
      mx = Math.max(mx, e);
    }
    long rest = s - mx;
    return mx > rest + 1 ? rest * 2 + 1 : s;
  }
}

```

### Python

```python
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

```

### CPP

```cpp
class Solution {
public:
  long long numberOfWeeks(vector<int> &milestones) {
    int mx = *max_element(milestones.begin(), milestones.end());
    long long s = accumulate(milestones.begin(), milestones.end(), 0LL);
    long long rest = s - mx;
    return mx > rest + 1 ? rest * 2 + 1 : s;
  }
};

```