Maximum Number of Weeks for Which You Can Work: Greedy Scheduling

You have n projects where milestones[i] is the number of weeks of work needed for project i. Each week you must work on exactly one project, and you cannot work on the same project for two consecutive weeks. Find the maximum number of weeks you can work.

This is LeetCode 1953: Maximum Number of Weeks for Which You Can Work, a medium problem that looks like it needs simulation or backtracking but actually reduces to a single comparison. The key is figuring out whether the largest project can be fully interleaved with the rest.

Why this problem matters

This problem is a clean example of greedy reasoning about resource balance. Instead of simulating week by week, you ask one question: does the largest project dominate? The answer to that question determines the entire result. This kind of "compare the max to everything else" pattern shows up in scheduling problems, task assignment, and frequency-based greedy problems like Task Scheduler and Reorganize String.

It also teaches you to avoid overcomplicating things. The brute force approach is tempting but unnecessary. Once you see the mathematical structure, the solution is a few lines of code.

The brute force approach

The most obvious approach is to simulate the scheduling process. Use a priority queue (max-heap) to always pick the project with the most remaining milestones, making sure you do not pick the same project as last week.

def number_of_weeks_brute(milestones):
    import heapq
    heap = [-m for m in milestones if m > 0]
    heapq.heapify(heap)
    weeks = 0
    last = -1

    while heap:
        top = heapq.heappop(heap)
        if -top == last and not heap:
            break
        if -top == last:
            second = heapq.heappop(heap)
            heapq.heappush(heap, top)
            top = second
        last = -top
        weeks += 1
        if -top - 1 > 0:
            heapq.heappush(heap, top + 1)

    return weeks

This works, but it runs in O(total * log n) time where total is the sum of all milestones. With milestones up to 10^9 and n up to 10^5, the total can be enormous. You would be simulating billions of weeks one at a time. That is far too slow.

The key insight: balancing the dominant project

Think of it like filling a schedule. You want to alternate between projects as much as possible. The only thing that can stop you is if one project has so many milestones that you run out of other projects to interleave with it.

Let max_val be the largest element in milestones and rest be the sum of all the other elements. There are two cases:

1. If max_val is <= rest + 1, you can always find a valid schedule that uses every single week. The answer is the total sum.
2. If max_val is greater than rest + 1, the largest project has too many weeks. You can pair each "rest" week with one "max" week, then squeeze in one more "max" week at the end. The answer is 2 * rest + 1.

Walking through it step by step

Let's trace through two examples. First, milestones = [5, 2, 1]: the max is 5, the rest sum to 3, and 5 > 3 + 1, so the largest project dominates. The answer is 2 * 3 + 1 = 7. Then, milestones = [1, 2, 3]: the max is 3, the rest sum to 3, and 3 <= 3 + 1, so all 6 weeks can be scheduled.

The algorithm does not need to actually build the schedule. It only needs to determine whether the max project dominates, which takes a single pass to compute the sum and max.

The greedy solution

Here is the complete solution in Python:

def number_of_weeks(milestones):
    total = sum(milestones)
    max_val = max(milestones)
    rest = total - max_val
    if max_val <= rest + 1:
        return total
    return 2 * rest + 1

Three variables, no loops beyond the built-in sum and max. Here is what each piece does:

1. total is the sum of all milestones. This is the best-case answer if every week can be scheduled.
2. max_val is the largest project. This is the one that might dominate the schedule.
3. rest is the sum of everything except the largest project. This determines how many "interleaving slots" are available.
4. The comparison max_val <= rest + 1 checks if the largest project can fit within the interleaving capacity. The "+1" accounts for the fact that the schedule can start with the max project, giving it one extra slot.

Why the greedy approach is correct

The correctness rests on one observation: the only constraint is that you cannot work on the same project two weeks in a row. The optimal strategy is always to alternate between the largest remaining project and anything else.

Case 1: max_val <= rest + 1. You can build a valid schedule by always picking the project with the most remaining milestones (as long as it is not the same as last week). Since no single project exceeds half the total (rounded up), you never get stuck. Every week gets used.

Case 2: max_val > rest + 1. The largest project has more milestones than all other projects combined can "absorb." Each rest week lets you do one more max week (by alternating), so you get rest pairs plus one more max week at the start or end. That gives 2 * rest + 1 total weeks. You cannot do better because you would need another non-max week to continue, and there are none left.

Complexity analysis

This is optimal. You need to look at every element at least once to determine the max and sum.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Max-vs-rest comparison

The pattern of comparing the largest element to the sum of all other elements:

total = sum(values)
max_val = max(values)
rest = total - max_val
if max_val <= rest + 1:
    ...

This same comparison appears in Reorganize String (can you rearrange characters so no two adjacent are the same?) and Task Scheduler (how many idle slots does the most frequent task force?). In all these problems, the "dominant element" determines whether the constraint can be satisfied.

2. Greedy scheduling by frequency

The broader pattern of scheduling tasks with cooldown or adjacency constraints by reasoning about frequencies rather than simulating. Instead of building the actual schedule, you compute bounds based on the most frequent item. This avoids O(total) simulation and gives O(n) solutions.

This pattern appears in problems like Task Scheduler, Reorganize String, and Distant Barcodes.

Edge cases

Before submitting, make sure your solution handles these:

• Single project milestones = [7]: max = 7, rest = 0. Since 7 > 0 + 1, the answer is 2 * 0 + 1 = 1. You can only work one week because there is nothing to alternate with.
• Two projects, balanced milestones = [3, 3]: max = 3, rest = 3. Since 3 <= 3 + 1, the answer is 6.
• All ones milestones = [1, 1, 1, 1]: max = 1, rest = 3. Since 1 <= 3 + 1, the answer is 4.
• One dominant project milestones = [100, 1, 1]: max = 100, rest = 2. Since 100 > 2 + 1, the answer is 2 * 2 + 1 = 5.

The greedy solution handles all of these without special-case logic.

Common mistakes

1. Simulating the schedule. The most common mistake is trying to build the actual week-by-week schedule using a heap or queue. This is correct but far too slow for the given constraints. The mathematical insight eliminates the need for simulation entirely.

2. Forgetting the +1 in the comparison. The condition is max_val <= rest + 1, not max_val <= rest. The "+1" matters because the schedule can start with the max project, giving it one extra slot before needing to alternate. Getting this wrong causes off-by-one errors on cases like milestones = [3, 3].

3. Using sorting instead of max. Some people sort the array to find the largest element. Sorting works but costs O(n log n), while max() is O(n). There is no need to know the order of the other elements.

From understanding to recall

You have read the greedy solution and it makes sense. One comparison, two cases. Simple. But can you write it from scratch in an interview without looking at it?

The details that trip people up: is it rest + 1 or just rest? Is the dominated case 2 * rest + 1 or 2 * (rest + 1)? These are small but critical distinctions, and they are easy to mix up under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the max-vs-rest comparison from scratch at increasing intervals. After a few rounds, the formula is automatic. You see "schedule tasks with no consecutive repeats" and the answer flows out without hesitation.

The max-vs-rest pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Task Scheduler - Another greedy scheduling problem where the most frequent element determines the answer
• Gas Station - A greedy problem where a single pass replaces brute-force simulation
• Reorganize String - Uses the same max-vs-rest frequency comparison to check if rearrangement is possible

CodeBricks breaks the maximum number of weeks LeetCode problem into its max-vs-rest and greedy-scheduling building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy scheduling question shows up in your interview, you do not think about it. You just write it.