Maximum Number of Weeks for Which You Can Work

Medium
1464.

Maximum Number of Weeks for Which You Can Work

Maximum Number of Weeks for Which You Can Work is a medium coding problem on arrays and greedy, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 10^5
  • 1 <= milestones[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} milestones
 * @return {number}
 */
var numberOfWeeks = function(milestones) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 10^5
  • 1 <= milestones[i] <= 10^4

Hints for Maximum Number of Weeks for Which You Can Work

  1. Hint 1

    Only the largest project can cause trouble — all the others can be interleaved with it.

  2. Hint 2

    Let rest be the total of all projects except the largest, mx. If mx <= rest + 1, everything can be finished.

  3. Hint 3

    Otherwise each of the rest milestones can separate two milestones of the big project: 2 · rest + 1 weeks.

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

  1. Compute total and mx = max(milestones); let rest = total - mx.
  2. If mx > rest + 1, return 2 · rest + 1.
  3. 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, not rest: 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 total

Java

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