1953. Maximum Number of Weeks for Which You Can Work
Problem Description
In this problem, we are given n
projects, each having a certain number of milestones that need to be completed. Each milestones[i]
represents the number of milestones for the i
th project. The goal is to work on these projects under two constraints:
- Each week, we complete exactly one milestone from one project. We must work every week without skipping any.
- We are not allowed to work on milestones from the same project for two consecutive weeks.
We are required to keep working on the projects until either all the milestones are completed or it becomes impossible to continue without breaking the rules. The task is to calculate the maximum number of weeks we can work on these projects without violating the given rules.
Intuition
To solve the problem, let's consider the following points:
-
If the number of milestones for one project is more than the sum of milestones of all other projects plus one (i.e.,
max(milestones) > sum(milestones) - max(milestones) + 1
), we will inevitably end up violating the rule about not working on the same project for two consecutive weeks. This is because after finishing all the milestones from other projects, we would still have at least two milestones left from the project with the maximum milestones, which would force us to work on the same project back-to-back. -
If the maximum number of milestones is less than or equal to the sum of the rest of the milestones plus one, we can always alternate between the project with the most milestones and the other projects.
With these insights, we arrive at the core of the solution:
- If
max(milestones)
(the largest number of milestones from any single project) is greater than the total milestones of all other projects plus one, we can work for2 * (total milestones of all other projects) + 1
weeks, because after that we will be left only with milestones from the project with the maximum milestones, which we cannot work on consecutively. - If the maximum milestones are less than or equal to the sum of all other milestones plus one, we can complete all the work without having any leftover milestones, working for
sum(milestones)
weeks.
By using this strategy, our code neatly captures the maximum number of weeks we can work.
Learn more about Greedy patterns.
Solution Approach
The solution is relatively straightforward and does not require complex data structures or algorithms. Here's the step-by-step approach:
-
First, we identify the project with the maximum number of milestones by using Python's
max()
function on our list of milestones. This gives us the maximum valuemx
. -
We also compute the sum of all milestones across all projects using the
sum()
function. This total is stored in the variables
. -
We then calculate the "rest" by subtracting the maximum number of milestones from the total sum,
rest = s - mx
. This represents the total milestones from projects other than the one with the maximum milestones. -
We use an
if
condition to check whether the maximum number of milestones is greater than the sum of milestones from other projects plus one (mx > rest + 1
). If true, this means we will eventually face a situation where we have to work on the same project for two consecutive weeks, which breaks the rules. In this case, the maximum number of weeks we can work isrest * 2 + 1
, because we can alternate between projects until the non-maximum projects are completed, leaving just one week left to work on the max project before breaking the rule. -
If the condition is false, it implies we can finish all milestones without breaking the rules. Hence, we can work for
s
weeks, which represents the total sum of milestones.
The pattern used here is primarily based on mathematical reasoning rather than applying specific algorithms or data structures. The key is to quickly calculate the total sum and the largest element and make a decision based on the constraints given in the problem.
The Python code provided encapsulates this logic succinctly in two lines, making use of Python's list operations to find the required max and sum values and performing a simple conditional operation to arrive at the result.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example with n
projects with their respective milestones: milestones = [3, 2, 2]
. In this case, the project with the maximum number of milestones (project 1) has 3 milestones.
Following the step-by-step solution approach:
- Identify the project with the maximum number of milestones:
mx = max(milestones)
gives usmx = 3
.
- Compute the sum of all milestones across all projects:
s = sum(milestones)
gives uss = 3 + 2 + 2 = 7
.
- Calculate the milestones from the other projects excluding the max project:
rest = s - mx
gives usrest = 7 - 3 = 4
.
- Check if we can avoid working on the same project for two consecutive weeks:
- We evaluate
mx > rest + 1
, which is3 > 4 + 1
. This condition is false.
- We evaluate
- Since the condition is false, it implies we will not have to work on the same project for two consecutive weeks at any point. Therefore, we can work on all milestones without breaking the rules:
- The maximum number of weeks we can work is
s
weeks, so the answer is7
weeks.
- The maximum number of weeks we can work is
In this scenario, a possible sequence could be working on projects in the following order over 7 weeks: 1, 2, 1, 3, 1, 2, 3
. Each time we work on the project with the maximum milestones (project 1), we alternate it with work on the other projects, ensuring we do not violate the constraint of working on the same project in consecutive weeks. By following the described approach, we've determined that we can work for a total of 7 weeks.
Solution Implementation
1from typing import List # Import List from the typing module for type hinting
2
3class Solution:
4 # Function to calculate the maximum number of weeks of work
5 def number_of_weeks(self, milestones: List[int]) -> int:
6 max_milestone = max(milestones) # Get the maximum value from milestones list
7 total_sum = sum(milestones) # Calculate the sum of all milestones
8 rest = total_sum - max_milestone # Calculate the sum of all other milestones except the maximum one
9
10 # If the maximum milestone is more than the sum of other milestones + 1,
11 # the maximum number of weeks we can work would be (rest * 2) + 1
12 # (work on other projects and on the max one alternatively).
13 if max_milestone > rest + 1:
14 return (rest * 2) + 1
15 else:
16 # Otherwise, we can work on all projects without any project taking
17 # an entire additional week on its own.
18 return total_sum
19
20# Example usage:
21# sol = Solution()
22# result = sol.number_of_weeks([1, 2, 3])
23# print(result) # This will print 6, as all milestones can be completed without restrictions
24
1class Solution {
2 public long numberOfWeeks(int[] milestones) {
3 int maxMilestone = 0; // Initialize variable to store the maximum value of milestones
4 long totalMilestonesSum = 0; // Initialize a variable to store the sum of all milestones
5
6 // Iterate through each milestone and calculate the total sum and max milestone
7 for (int milestone : milestones) {
8 totalMilestonesSum += milestone; // Add the current milestone to the total sum
9 maxMilestone = Math.max(maxMilestone, milestone); // Update max milestone if the current one is greater
10 }
11
12 // Calculate the sum of all milestones except the maximum one
13 long rest = totalMilestonesSum - maxMilestone;
14
15 // If the maximum milestone is more than the sum of the rest plus one,
16 // then return twice the sum of the rest plus one as maximum weeks
17 // This ensures that we cannot complete the maximum milestone if it's too large compared to the others
18 if (maxMilestone > rest + 1) {
19 return rest * 2 + 1;
20 } else {
21 // Otherwise, return the total sum of all milestones meaning all milestones can be completed
22 return totalMilestonesSum;
23 }
24 }
25}
26
1class Solution {
2public:
3 long long numberOfWeeks(vector<int>& milestones) {
4 // Find the largest milestone.
5 int maxMilestone = *max_element(milestones.begin(), milestones.end());
6
7 // Calculate the total sum of all milestones.
8 long long sum = accumulate(milestones.begin(), milestones.end(), 0LL);
9
10 // Calculate the total sum of all milestones excluding the largest one.
11 long long sumWithoutMax = sum - maxMilestone;
12
13 // If the largest milestone is greater than the sum of the rest plus one,
14 // we can only work on each project without exceeding the maximum until we
15 // complete projects that amount to double the rest (evenly distributed)
16 // and then finish one more week of work on the largest one.
17 if (maxMilestone > sumWithoutMax + 1) {
18 return sumWithoutMax * 2 + 1;
19 } else {
20 // Otherwise, we can complete all weeks of work without any problem.
21 // In this case, sum of all milestones equals total number of weeks.
22 return sum;
23 }
24 }
25};
26
1function numberOfWeeks(milestones: number[]): number {
2 // Find the largest milestone.
3 const maxMilestone = Math.max(...milestones);
4
5 // Calculate the total sum of all milestones.
6 const sum = milestones.reduce((a, b) => a + b, 0);
7
8 // Calculate the total sum of all milestones, excluding the largest one.
9 const sumWithoutMax = sum - maxMilestone;
10
11 // Check if the largest milestone is greater than the sum of the rest plus one.
12 // If so, we are limited by how many weeks we can work without exceeding the maximum.
13 if (maxMilestone > sumWithoutMax + 1) {
14 // Return the maximum possible number of weeks we can work without exceeding the largest milestone.
15 // This is twice the sum of the other milestones plus one week on the largest project.
16 return sumWithoutMax * 2 + 1;
17 } else {
18 // Otherwise, we can complete all weeks of work on all projects without any issues.
19 // In this case, the sum of all milestones equals the total number of possible weeks of work.
20 return sum;
21 }
22}
23
Time and Space Complexity
Time Complexity
The time complexity of the solution is O(N)
, where N
is the number of elements in the milestones
list. This is because the algorithm needs to iterate through all elements twice: once to calculate the sum s
, and once to find the maximum value mx
in the list.
Space Complexity
The space complexity of the solution is O(1)
. It only uses a constant amount of extra space to store variables mx
, s
, and rest
, regardless of the size of the input list milestones
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first