Skip to main content
Talentd

Maximum Number of Weeks for Which You Can Work - Solution & Explanation

MediumArrayGreedy16 min readAsked at: Amazon, Wells Fargo, NatWest
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array where milestones[i] represents the number of tasks in the i-th project. Each week you complete exactly one task, but you cannot work on the same project in two consecutive weeks. The goal is to compute the maximum number of weeks you can keep working under this constraint.

Approach 1: Greedy with Max Milestone Constraint (O(n) time, O(1) space)

The key observation is that the project with the largest milestone count determines whether you can keep alternating projects indefinitely. First compute the total number of tasks total and the largest milestone value maxMilestone. If the largest project is not larger than the sum of the rest (maxMilestone ā‰¤ total - maxMilestone + 1), you can interleave tasks from other projects and complete all tasks. If the largest project dominates, eventually you will be forced to repeat the same project. In that case the schedule alternates until other projects run out, giving a maximum of 2 * (total - maxMilestone) + 1 weeks. This greedy counting method avoids simulation and works in a single pass over the array. The logic relies on balancing tasks between projects, which is a classic greedy strategy.

Approach 2: Priority Queue (Heap) Simulation (O(n log n) time, O(n) space)

Another way is to simulate the scheduling process using a max heap. Push all project task counts into a priority queue. Each week you pick the project with the most remaining tasks that is different from the one used in the previous week. After completing a task, decrement its count and push it back if tasks remain. If the heap only contains the same project as the previous week, the schedule stops. This approach mirrors the real scheduling process and makes the constraint explicit, but it performs log n heap operations for each step.

Recommended for interviews: The greedy formula using the maximum milestone constraint is the expected solution. It reduces the entire scheduling problem to a simple mathematical bound with O(n) time and O(1) space. The heap approach demonstrates understanding of task scheduling but is slower and unnecessary once you recognize the greedy pattern.

Approach 1: Greedy Approach with Max Milestone Constraint

To maximize the number of weeks, consider the project with the most milestones. If it has more milestones than all other projects combined, you can work (sum of all milestones + 1) // 2 weeks before being forced to stop. Otherwise, you can work a week for each milestone.

We calculate the total milestones and identify the project with the maximum milestones. If this project can dominate the project work, calculate using 2 * (total - max) + 1; otherwise, the total gives the number of weeks.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) due to single pass to find total and max milestone.
Space Complexity: O(1) as no additional space is used.

Try this approach in the editor ā†’

Approach 2: Alternative Priority Queue (Heap) Approach

Using a max-heap data structure, we ensure the largest available milestone count is always processed to maintain diversity and ensure no consecutive week project milestone violation. This approach involves repeatedly selecting and adjusting milestones in a greedy manner using a priority queue to simulate this efficiently.

A max heap ensures we always work on the most available project milestones first. By popping two projects and reducing their counts, we simulate back-to-back work on different projects, preserving rules.

Code

C++JavaPython

C++

Java

Python

Complexity

Time Complexity: O(n log n) due to use of heap operations.
Space Complexity: O(n) to maintain the priority queue structure.

Try this approach in the editor ā†’

Approach 3: Greedy

We consider under what circumstances we cannot complete all stage tasks. If there is a project i whose number of stage tasks is greater than the sum of the number of stage tasks of all other projects plus 1, then we cannot complete all stage tasks. Otherwise, we can definitely complete all stage tasks by interlacing between different projects.

We denote the sum of the number of stage tasks of all projects as s, and the maximum number of stage tasks as mx, then the sum of the number of stage tasks of all other projects is rest = s - mx.

If mx > rest + 1, then we cannot complete all stage tasks, and at most we can complete rest times 2 + 1 stage tasks. Otherwise, we can complete all stage tasks, the number is s.

The time complexity is O(n), where n is the number of projects. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Greedy Approach with Max Milestone Constraint

Time Complexity: O(n) due to single pass to find total and max milestone.
Space Complexity: O(1) as no additional space is used.

Alternative Priority Queue (Heap) Approach

Time Complexity: O(n log n) due to use of heap operations.
Space Complexity: O(n) to maintain the priority queue structure.

Greedyā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Max Milestone ConstraintO(n)O(1)Best general solution. Uses total tasks and largest project to compute the maximum possible schedule length.
Priority Queue (Heap) SimulationO(n log n)O(n)Useful for understanding or simulating scheduling where the largest remaining task must be selected each step.

Video Solution

1953. Maximum Number of Weeks for Which You Can (Leetcode Medium) ā€¢ Programming Live with Larry ā€¢ 2,983 views views

Watch 5 more video solutions ā†’

Frequently Asked Questions

Is Maximum Number of Weeks for Which You Can Work easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 40%. The difficulty comes from recognizing the greedy constraint involving the largest project rather than attempting to simulate the schedule.
Maximum Number of Weeks for Which You Can Work Python/Java solution
Most implementations compute the total tasks and maximum milestone, then return either the total or the formula 2 * (total - maxMilestone) + 1. This logic translates directly to Python, Java, C++, C#, and JavaScript with a single loop and constant extra space.
How to solve Maximum Number of Weeks for Which You Can Work in O(n)?
Iterate through the milestones array to compute the total sum and the largest milestone value. If the largest value is less than or equal to total minus itself plus one, all tasks can be scheduled, so the answer is total. Otherwise the answer becomes 2 * (total - maxMilestone) + 1 because the largest project eventually forces a repeat.
What is the best approach for Maximum Number of Weeks for Which You Can Work?
The optimal solution uses a greedy observation based on the largest project. Compute the total number of tasks and the maximum milestone count. If the largest project does not exceed the sum of the rest, you can complete all tasks. Otherwise the maximum schedule length becomes 2 * (total - maxMilestone) + 1. This runs in O(n) time and O(1) space.
Is Maximum Number of Weeks for Which You Can Work asked at Google/Amazon/Meta?
Greedy scheduling and workload balancing problems similar to this appear frequently in interviews at companies like Google, Amazon, and Meta. The pattern of checking whether one element dominates the rest is common in greedy interview questions involving task distribution.
What data structure is used in Maximum Number of Weeks for Which You Can Work?
The optimal solution only requires simple variables to track the total and the maximum value from the array. An alternative approach uses a priority queue (max heap) to simulate picking the project with the largest remaining tasks each week.
What is the time complexity of Maximum Number of Weeks for Which You Can Work?
The optimal greedy approach runs in O(n) time because it only requires a single pass to compute the total tasks and the maximum milestone value. The space complexity is O(1). A heap-based simulation alternative takes O(n log n) time due to repeated priority queue operations.

Ready to solve this problem?

Practice Maximum Number of Weeks for Which You Can Work with our built-in code editor and test cases.

Practice on FleetCode
Previous

Task Scheduler