Problem

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 themaximum number of weeks you would be able to work on the projects without violating the rules mentioned above.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

Method 1 – Greedy Scheduling

Intuition

If the largest project has too many milestones, you will eventually be forced to work on it in consecutive weeks, which is not allowed. The optimal strategy is to alternate between the largest project and the rest as much as possible. If the largest project has at most half the total milestones, you can finish all. Otherwise, you can only finish up to 2 * (sum of other milestones) + 1 weeks.

Approach

  1. Compute the total number of milestones and the maximum milestones in any project.
  2. If the largest project has at most half the total, return the total milestones.
  3. Otherwise, return 2 * (total - max) + 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    long long numberOfWeeks(vector<int>& milestones) {
        long long sum = 0, mx = 0;
        for (int x : milestones) {
            sum += x;
            mx = max(mx, (long long)x);
        }
        return mx <= sum - mx ? sum : 2 * (sum - mx) + 1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func numberOfWeeks(milestones []int) int64 {
    var sum, mx int64
    for _, x := range milestones {
        sum += int64(x)
        if int64(x) > mx {
            mx = int64(x)
        }
    }
    if mx <= sum-mx {
        return sum
    }
    return 2*(sum-mx) + 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public long numberOfWeeks(int[] milestones) {
        long sum = 0, mx = 0;
        for (int x : milestones) {
            sum += x;
            mx = Math.max(mx, x);
        }
        return mx <= sum - mx ? sum : 2 * (sum - mx) + 1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun numberOfWeeks(milestones: IntArray): Long {
        var sum = 0L
        var mx = 0L
        for (x in milestones) {
            sum += x
            mx = maxOf(mx, x.toLong())
        }
        return if (mx <= sum - mx) sum else 2 * (sum - mx) + 1
    }
}
1
2
3
4
5
6
7

class Solution:
    def numberOfWeeks(self, milestones: list[int]) -> int:
        s = sum(milestones)
        mx = max(milestones)
        if mx <= s - mx:
            return s
        return 2 * (s - mx) + 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn number_of_weeks(milestones: Vec<i32>) -> i64 {
        let sum: i64 = milestones.iter().map(|&x| x as i64).sum();
        let mx: i64 = *milestones.iter().max().unwrap() as i64;
        if mx <= sum - mx {
            sum
        } else {
            2 * (sum - mx) + 1
        }
    }
}
1
2
3
4
5
6
7
8

class Solution {
    numberOfWeeks(milestones: number[]): number {
        const sum = milestones.reduce((a, b) => a + b, 0);
        const mx = Math.max(...milestones);
        if (mx <= sum - mx) return sum;
        return 2 * (sum - mx) + 1;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the milestones array once.
  • 🧺 Space complexity: O(1) — Only a few variables are used.