342. Sack Splitting
A warehouse has n sacks of grain, and bags[i] is the number of kilograms in the i-th sack. In one operation, a worker takes any sack and divides it into two new sacks that both contain a positive number of kilograms. At most maxOps operations may be performed in total.
The penalty of the final set of sacks is the weight of the heaviest sack. Return the smallest penalty that can be reached using at most maxOps operations. Splitting a sack of weight w so that no piece is heavier than x needs ceil(w / x) - 1 operations, which helps you decide whether a penalty is reachable.
Example 1
- Input:
- bags = [7,4], maxOps = 3
- Output:
- 3
- Explanation:
To keep every sack at 3 kg or less, the 7 kg sack needs 2 operations (3, 3, 1) and the 4 kg sack needs 1 (3, 1), which is 3 operations. For 2 kg we would need 3 + 1 = 4 operations, so 3 is the best penalty.
Example 2
- Input:
- bags = [8,5,2], maxOps = 1
- Output:
- 5
- Explanation:
With one operation we can split the 8 kg sack into 4 and 4, but then the 5 kg sack is still the heaviest. Splitting 8 into 5 and 3 gives a maximum of 5. So the answer is 5.
Constraints
1 ≤ bags.length ≤ 105
1 ≤ bags[i] ≤ 109
0 ≤ maxOps ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log M), where M is the heaviest sack
- Space
- O(1)