Watch 6 video solutions for Maximum Number of Weeks for Which You Can Work, a medium level problem involving Array, Greedy. This walkthrough by Programming Live with Larry has 2,955 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |