599. Fill the Bags
A landscaper has several planters. Planter i can hold at most capacity[i] decorative rocks and currently holds rocks[i] of them. A planter is full when it holds at least its capacity (a planter that already holds more rocks than its capacity is simply full and needs nothing).
The landscaper also carries extra loose rocks and may drop any number of them into any planters, and a planter needs no more than enough rocks to reach its capacity. Rocks do not have to be used up. Return the largest number of planters that can be full after distributing the loose rocks. Planters that are already full count. Aim for O(n log n) time and O(n) space.
Example 1
- Input:
- capacity = [5,4,6], rocks = [2,4,1], extra = 5
- Output:
- 2
- Explanation:
The needs are 3, 0 and 5; filling the 0 and the 3 uses 3 rocks, and the 5 does not fit in the remaining 2, so the answer is 2.
Example 2
- Input:
- capacity = [3,3,3], rocks = [0,0,0], extra = 6
- Output:
- 2
- Explanation:
Each planter needs 3, so 6 extra rocks fill exactly two planters.
Example 3
- Input:
- capacity = [10,8], rocks = [1,1], extra = 4
- Output:
- 0
- Explanation:
The needs are 9 and 7, both more than 4 extra rocks, so no planter can be filled and the answer is 0.
Constraints
1 ≤ n ≤ 200000, wheren = capacity.length = rocks.length1 ≤ capacity[i] ≤ 100000 ≤ rocks[i] ≤ 10000(it may exceedcapacity[i])0 ≤ extra ≤ 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 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)