LeetCode 1953 - Maximum Number of Weeks for Which You Can Work

The problem gives us an array called milestones, where each value represents how many milestones belong to a particular project. Every week, we must complete exactly one milestone from one project.

leetcodemediumarraygreedy

LeetCode Problem 1953

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives us an array called milestones, where each value represents how many milestones belong to a particular project. Every week, we must complete exactly one milestone from one project. However, there is an important restriction: we are not allowed to work on the same project in two consecutive weeks.

Our goal is to determine the maximum number of weeks we can continue working while obeying this rule.

The input array represents independent projects. For example, if:

milestones = [1, 2, 3]

then:

  • Project 0 has 1 milestone
  • Project 1 has 2 milestones
  • Project 2 has 3 milestones

The output is the maximum number of weeks we can schedule work without ever selecting the same project in back to back weeks.

The constraints are important:

  • n can be as large as 10^5
  • Each milestone count can be as large as 10^9

This immediately tells us that any simulation involving week by week scheduling with priority queues or backtracking would be too slow in the worst case. The total number of milestones could be enormous, potentially up to 10^14, so we cannot explicitly build the schedule.

The key challenge is understanding when the scheduling restriction prevents us from finishing all milestones.

The most important edge case is when one project contains far more milestones than all other projects combined. For example:

[10, 1, 1]

Even though there are 12 total milestones, we cannot finish all of them because eventually the large project will be forced to appear consecutively.

Another important edge case is when the milestones are balanced enough that we can alternate projects indefinitely. In that case, we can complete every milestone.

The problem guarantees:

  • Every project has at least one milestone
  • The array is non-empty
  • All values are positive integers

This simplifies the implementation because we never need to handle empty projects.

Approaches

Brute Force Approach

A brute force strategy would attempt to explicitly simulate the schedule week by week.

One possible implementation is:

  1. Always choose the project with the largest remaining milestone count that is different from the previously selected project.
  2. Reduce its count.
  3. Continue until no valid project remains.

A max heap could help efficiently choose the next project.

This approach is correct because it greedily tries to maximize future flexibility by consuming large projects first while avoiding consecutive duplicates.

However, the total number of milestones can be extremely large. Consider:

milestones[i] = 10^9

The total number of weeks could exceed 10^14. Simulating every week would therefore be far too slow.

Even with a heap, the complexity would be proportional to the total number of milestones, which is infeasible.

Key Insight

The problem is actually governed by a simple mathematical condition.

Suppose:

  • total = total number of milestones
  • maxMilestone = largest project size
  • rest = sum of all other projects

The only project that can cause trouble is the largest one.

To avoid consecutive weeks on the same project, milestones from the largest project must be separated by milestones from other projects.

If the largest project has:

maxMilestone <= rest + 1

then the other projects provide enough separators, and we can complete all milestones.

For example:

[3,2,1]

Largest project = 3

Rest = 3

Possible arrangement:

A B A C A B

All milestones are completed.

But if:

maxMilestone > rest + 1

then eventually the largest project runs out of separators.

For example:

[5,2,1]

Largest project = 5

Rest = 3

We can arrange:

A B A B A C A

At this point, only one A remains, but placing it would create consecutive As.

The maximum workable weeks become:

2 * rest + 1

because each non-largest milestone can separate two milestones from the largest project.

This observation reduces the entire problem to simple arithmetic.

Approach Time Complexity Space Complexity Notes
Brute Force O(total milestones log n) O(n) Simulates weekly scheduling using a heap
Optimal O(n) O(1) Uses mathematical observation about the largest project

Algorithm Walkthrough

  1. Compute the total number of milestones across all projects.

This represents the theoretical maximum number of weeks if every milestone can be completed. 2. Find the project with the maximum number of milestones.

This is the only project that can potentially violate the scheduling rule. 3. Compute the sum of all remaining milestones.

rest = total - maxMilestone

These milestones act as separators between milestones of the largest project. 4. Check whether the largest project can be fully interleaved.

If:

$maxMilestone \leq rest + 1$

then we can schedule every milestone successfully. 5. If the condition holds, return the total number of milestones.

Since enough separators exist, every milestone can be completed. 6. Otherwise, the largest project dominates too heavily.

In this case, the maximum achievable schedule length is:

$2 \cdot rest + 1$

because each remaining milestone can separate two milestones from the largest project, except for one extra largest-project milestone at the beginning or end.

Why it works

The correctness depends on the interleaving property.

To avoid consecutive selections from the same project, milestones from the largest project must be separated by milestones from other projects. If the number of separators is sufficient, all milestones can be arranged safely.

When separators are insufficient, the schedule inevitably ends with two consecutive milestones from the same largest project. The maximum valid arrangement alternates as long as possible, producing exactly:

largest, other, largest, other, ...

This yields 2 * rest + 1 total weeks.

Therefore, the formula always computes the optimal answer.

Python Solution

from typing import List

class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        total_milestones = sum(milestones)
        max_milestone = max(milestones)

        remaining = total_milestones - max_milestone

        if max_milestone <= remaining + 1:
            return total_milestones

        return 2 * remaining + 1

The implementation begins by computing the total number of milestones and identifying the largest project.

Next, it calculates how many milestones belong to all other projects combined. These milestones are the separators needed to prevent consecutive work on the largest project.

The condition:

max_milestone <= remaining + 1

checks whether full interleaving is possible.

If it is, we return the total number of milestones because every project can be completed.

Otherwise, we apply the mathematical limit:

2 * remaining + 1

which represents the longest valid alternating schedule.

The implementation is extremely compact because the difficult scheduling behavior has already been reduced to a simple counting argument.

Go Solution

func numberOfWeeks(milestones []int) int64 {
    var total int64 = 0
    var maxMilestone int64 = 0

    for _, value := range milestones {
        current := int64(value)

        total += current

        if current > maxMilestone {
            maxMilestone = current
        }
    }

    remaining := total - maxMilestone

    if maxMilestone <= remaining+1 {
        return total
    }

    return 2*remaining + 1
}

The Go implementation follows the same logic as the Python version.

One important Go-specific detail is the use of int64. The total number of milestones can become very large, potentially exceeding the range of a standard 32-bit integer. Using int64 prevents overflow.

The algorithm itself remains identical:

  • Compute total milestones
  • Find the largest project
  • Determine whether full interleaving is possible
  • Return either the full total or the restricted maximum schedule length

Worked Examples

Example 1

milestones = [1,2,3]

Step 1: Compute totals

Variable Value
total 6
maxMilestone 3
remaining 3

Step 2: Check feasibility

Condition:

$3 \leq 3 + 1$

This is true.

Step 3: Return answer

Answer = total = 6

A valid arrangement is:

Week Project
1 0
2 2
3 1
4 2
5 1
6 2

All milestones are completed.

Example 2

milestones = [5,2,1]

Step 1: Compute totals

Variable Value
total 8
maxMilestone 5
remaining 3

Step 2: Check feasibility

Condition:

$5 \leq 3 + 1$

This is false.

Step 3: Apply restricted formula

$2 \cdot 3 + 1 = 7$

Step 4: Construct schedule

Week Project
1 0
2 1
3 0
4 1
5 0
6 2
7 0

One milestone from project 0 remains unfinished.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the array once to compute the sum and maximum
Space O(1) Only a few variables are used

The algorithm is optimal because every input element must be examined at least once to determine the total and maximum milestone counts. No auxiliary data structures proportional to input size are required.

Test Cases

from typing import List

class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        total_milestones = sum(milestones)
        max_milestone = max(milestones)

        remaining = total_milestones - max_milestone

        if max_milestone <= remaining + 1:
            return total_milestones

        return 2 * remaining + 1

solution = Solution()

assert solution.numberOfWeeks([1, 2, 3]) == 6  # Provided example, all milestones usable
assert solution.numberOfWeeks([5, 2, 1]) == 7  # Provided example, one milestone unused

assert solution.numberOfWeeks([1]) == 1  # Single project with one milestone
assert solution.numberOfWeeks([10]) == 1  # Single project cannot repeat consecutively

assert solution.numberOfWeeks([2, 2]) == 4  # Perfect alternation
assert solution.numberOfWeeks([3, 3, 3]) == 9  # Fully balanced projects

assert solution.numberOfWeeks([7, 1]) == 3  # Dominant project with minimal separator
assert solution.numberOfWeeks([8, 4]) == 9  # Largest project partially usable

assert solution.numberOfWeeks([1000000000, 1000000000]) == 2000000000  # Large values
assert solution.numberOfWeeks([1000000000, 1, 1]) == 5  # Very large dominant project

assert solution.numberOfWeeks([4, 1, 1, 1]) == 7  # Exactly enough separators
assert solution.numberOfWeeks([6, 1, 1, 1]) == 7  # Not enough separators
Test Why
[1,2,3] Standard fully schedulable case
[5,2,1] Dominant project prevents completion
[1] Smallest valid input
[10] Single large project edge case
[2,2] Simple alternating schedule
[3,3,3] Balanced multi-project input
[7,1] Extremely dominant project
[8,4] Partial completion scenario
[1000000000,1000000000] Large integer handling
[1000000000,1,1] Large dominant project stress test
[4,1,1,1] Boundary where full completion is still possible
[6,1,1,1] Boundary where full completion becomes impossible

Edge Cases

Single Project

If there is only one project, we can only work for one week regardless of how many milestones it contains.

For example:

[10]

After completing one milestone, the next week would require working on the same project consecutively, which is forbidden.

The formula handles this naturally:

remaining = 0
answer = 2 * 0 + 1 = 1

Largest Project Exactly Fits

Consider:

[4,1,1,1]

Here:

maxMilestone = 4
remaining = 3

The condition becomes:

$4 \leq 3 + 1$

This is exactly true, meaning a perfect interleaving exists.

A valid schedule is:

A B A C A D A

The implementation correctly returns all 7 milestones.

Largest Project Too Large

Consider:

[10,1,1]

The largest project heavily dominates the schedule.

Even after using all smaller projects as separators:

A B A C A

we still cannot place the remaining A milestones without violating the rules.

The implementation correctly limits the result to:

$2 \cdot 2 + 1 = 5$

rather than incorrectly returning the total milestone count.