1953. Maximum Number of Weeks for Which You Can Work LeetCode Solution

In this guide, you will get 1953. Maximum Number of Weeks for Which You Can Work LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Weeks for Which You Can Work problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Maximum Number of Weeks for Which You Can Work solution in C++
  4. Maximum Number of Weeks for Which You Can Work solution in Java
  5. Maximum Number of Weeks for Which You Can Work solution in Python
  6. Additional Resources
1953. Maximum Number of Weeks for Which You Can Work LeetCode Solution image

Problem Statement of Maximum Number of Weeks for Which You Can Work

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.

See also  2245. Maximum Trailing Zeros in a Cornered Path LeetCode Solution

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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)
See also  806. Number of Lines To Write String LeetCode Solution

1953. Maximum Number of Weeks for Which You Can Work LeetCode Solution in C++

class Solution {
 public:
  long long numberOfWeeks(vector<int>& milestones) {
    // The best strategy is to pick "max, nonMax, max, nonMax, ...".
    const int mx = ranges::max(milestones);
    const long sum = accumulate(milestones.begin(), milestones.end(), 0L);
    const long nonMax = sum - mx;
    return min(sum, 2 * nonMax + 1);
  }
};
/* code provided by PROGIEZ */

1953. Maximum Number of Weeks for Which You Can Work LeetCode Solution in Java

class Solution {
  public long numberOfWeeks(int[] milestones) {
    // The best strategy is to pick "max, nonMax, max, nonMax, ...".
    final int mx = Arrays.stream(milestones).max().getAsInt();
    final long sum = Arrays.stream(milestones).asLongStream().sum();
    final long nonMax = sum - mx;
    return Math.min(sum, 2 * nonMax + 1);
  }
}
// code provided by PROGIEZ

1953. Maximum Number of Weeks for Which You Can Work LeetCode Solution in Python

class Solution:
  def numberOfWeeks(self, milestones: list[int]) -> int:
    # The best strategy is to pick 'max, nonMax, max, nonMax, ...'.
    summ = sum(milestones)
    nonMax = summ - max(milestones)
    return min(summ, 2 * nonMax + 1)
# code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.