1724. Two Cups a Second
A beverage machine must fill counts[i] cups of drink type i. Each second it can either fill one cup of any type, or fill two cups of two different types at the same moment. Cups of the same type can never be filled in the same second.
Return the minimum number of seconds needed to fill every cup, as a long. Repeatedly pairing the two types with the most remaining cups is optimal, and it collapses to a closed form: the answer is the larger of the biggest count and half of the total cups rounded up. Aim for O(n) time and O(1) extra space. A count of 0 means that type needs nothing.
Example 1
- Input:
- counts = [1,4,2]
- Output:
- 4
- Explanation:
The 4-cup type needs 4 seconds on its own, and the remaining 3 cups can ride along in those seconds, so the answer is 4.
Example 2
- Input:
- counts = [2,2,2]
- Output:
- 3
- Explanation:
Six cups, two per second, and pairing across types is always possible: 3 seconds.
Example 3
- Input:
- counts = [5,1,1]
- Output:
- 5
- Explanation:
The type with 5 cups can only be paired with one other cup per second, so it alone needs 5 seconds.
Constraints
1 ≤ counts.length ≤ 1000
0 ≤ counts[i] ≤ 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 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)