Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1953.html

1953. Maximum Number of Weeks for Which You Can Work

Level

Medium

Description

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 i-th 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.

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 <= 10^5
  • 1 <= milestones[i] <= 10^9

Solution

Find the maximum of milestones, and calculate the sum of all elements in milestones. If the maximum is less than or equal to the sum of the remaining elements, then it is always possible to find two different projects for two adjacent weeks, so return the sum. Otherwise, return the remaining sum multipled by 2 plus 1.

  • class Solution {
    public long numberOfWeeks(int[] milestones) {
        Arrays.sort(milestones);
        int length = milestones.length;
        int maxMilestone = milestones[length - 1];
        long sum = 0;
        for (int milestone : milestones)
            sum += milestone;
        long remaining = sum - maxMilestone;
        if (remaining >= maxMilestone)
            return sum;
        else
            return remaining * 2 + 1;
    }
}

############

class Solution {
    public long numberOfWeeks(int[] milestones) {
        int mx = 0;
        long s = 0;
        for (int e : milestones) {
            s += e;
            mx = Math.max(mx, e);
        }
        long rest = s - mx;
        return mx > rest + 1 ? rest * 2 + 1 : s;
    }
}

  • // OJ: https://leetcode.com/problems/maximum-number-of-weeks-for-which-you-can-work/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    long long numberOfWeeks(vector<int>& A) {
        long long mx = *max_element(begin(A), end(A)), sum = accumulate(begin(A), end(A), 0L) - mx;
        return mx > sum ? sum * 2 + 1 : mx + sum; 
    }
};

  • class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        mx, s = max(milestones), sum(milestones)
        rest = s - mx
        return rest * 2 + 1 if mx > rest + 1 else s

############

# 1953. Maximum Number of Weeks for Which You Can Work
# https://leetcode.com/problems/maximum-number-of-weeks-for-which-you-can-work

class Solution:
    def numberOfWeeks(self, milestones: List[int]) -> int:
        ssum, mmax = sum(milestones), max(milestones)
        
        if ssum - mmax >= mmax: return ssum
        
        return 2 * (ssum - mmax) + 1


  • func numberOfWeeks(milestones []int) int64 {
	mx, s := 0, 0
	for _, e := range milestones {
		mx = max(mx, e)
		s += e
	}
	rest := s - mx
	if mx > rest+1 {
		return int64(rest*2 + 1)
	}
	return int64(s)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

All Problems

All Solutions