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:
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.length1 <= n <= 1051 <= milestones[i] <= 109Problem 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.
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.
Time Complexity: O(n) due to single pass to find total and max milestone.
Space Complexity: O(1) as no additional space is used.
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.
Time Complexity: O(n log n) due to use of heap operations.
Space Complexity: O(n) to maintain the priority queue structure.
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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach with Max Milestone Constraint | Time Complexity: O(n) due to single pass to find total and max milestone. |
| Alternative Priority Queue (Heap) Approach | Time Complexity: O(n log n) due to use of heap operations. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Max Milestone Constraint | O(n) | O(1) | Best general solution. Uses total tasks and largest project to compute the maximum possible schedule length. |
| Priority Queue (Heap) Simulation | O(n log n) | O(n) | Useful for understanding or simulating scheduling where the largest remaining task must be selected each step. |
1953. Maximum Number of Weeks for Which You Can (Leetcode Medium) • Programming Live with Larry • 2,955 views views
Watch 5 more video solutions →Practice Maximum Number of Weeks for Which You Can Work with our built-in code editor and test cases.
Practice on FleetCode