Maximum Number of Weeks for Which You Can Work — Solution
Maximum Number of Weeks for Which You Can Work solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Number of Weeks for Which You Can Work is a medium coding problem on arrays and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You run n projects; project i has milestones[i] milestones. Each week you finish exactly one milestone of one project, and you must work every week. You may never work on the same project two weeks in a row.
You stop as soon as every milestone is done, or when the only remaining work would break the rule. Return the maximum number of weeks you can work.
The original allows up to 10^9 milestones per project; here each count is at most 10^4 so the answer fits in a 32-bit integer.
Example 1
Input: milestones = [1,2,3]
Output: 6
Explanation: Working on projects 2, 1, 2, 0, 2, 1 in that order finishes everything.
Example 2
Input: milestones = [6,2,1]
Output: 7
Explanation: Project 0 has too many milestones: you can interleave it with the other three, giving 0, 1, 0, 1, 0, 2, 0.
Example 3
Input: milestones = [4]
Output: 1
Constraints
n == milestones.length1 <= n <= 10^51 <= milestones[i] <= 10^4
Hints for Maximum Number of Weeks for Which You Can Work
Hint 1
Only the largest project can cause trouble — all the others can be interleaved with it.
Hint 2
Let
restbe the total of all projects except the largest,mx. Ifmx <= rest + 1, everything can be finished.Hint 3
Otherwise each of the
restmilestones can separate two milestones of the big project:2 · rest + 1weeks.
How to solve Maximum Number of Weeks for Which You Can Work
Compare the biggest project mx with the sum of the others, rest. If it is not more than rest + 1, all milestones fit; otherwise the big project can be used only rest + 1 times, alternating with the others.
Approach
- Compute
totalandmx = max(milestones); letrest = total - mx. - If
mx > rest + 1, return2 · rest + 1. - Otherwise return
total.
Why it works
Two weeks on the big project need a different project between them, so it can be worked at most rest + 1 times — that gives the bound 2 · rest + 1 when mx is larger. When mx <= rest + 1, greedily working on the project with the most remaining milestones (other than last week's) never gets stuck before everything is done, because no project ever exceeds the rest by more than one.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- With the original bounds the answer needs 64 bits; keep a 64-bit total in fixed-width languages anyway.
- The threshold is
rest + 1, notrest: the big project may start and end the schedule. - A single project gives exactly one week.
Reference solution
Python
from typing import List
def numberOfWeeks(milestones: List[int]) -> int:
total = sum(milestones)
mx = max(milestones)
rest = total - mx
return 2 * rest + 1 if mx > rest + 1 else totalJava
public static int numberOfWeeks(int[] milestones) {
long total = 0;
int mx = 0;
for (int v : milestones) { total += v; mx = Math.max(mx, v); }
long rest = total - mx;
return (int) (mx > rest + 1 ? 2 * rest + 1 : total);
}C++
int numberOfWeeks(vector<int>& milestones) {
long long total = 0;
int mx = 0;
for (int v : milestones) { total += v; mx = max(mx, v); }
long long rest = total - mx;
return (int)(mx > rest + 1 ? 2 * rest + 1 : total);
}JavaScript
var numberOfWeeks = function(milestones) {
var total = 0, mx = 0;
for (var i = 0; i < milestones.length; i++) {
total += milestones[i];
if (milestones[i] > mx) mx = milestones[i];
}
var rest = total - mx;
return mx > rest + 1 ? 2 * rest + 1 : total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms