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 ith 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) + 1weeks, 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.
Which algorithm should you use to find a node that is close to the root of the tree?
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
ifcondition 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
sweeks, 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.
Which of these properties could exist for a graph but not a tree?
Example 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 - mxgives 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
sweeks, so the answer is7weeks.
- 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
241class 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}
261class 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};
261function 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}
23What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Time 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 of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.