mediumGreedyPattern: Greedy
Minimum Bins for Sequentially Sorted Items Solution
Problem Statement
You are given an array of positive integers `items`, where `items[i]` represents the size of the i-th item. The array `items` is guaranteed to be sorted in *descending order*. You are also provided an integer `binCapacity`, denoting the maximum total size of items that can be placed in any single bin. All items must be placed into bins sequentially, strictly preserving their order from `items[0]` to `items[items.length - 1]`. An individual item cannot be split and must fit entirely within one bin. Your task is to compute the minimum total number of bins required to accommodate all given items under these conditions.
Examples
Example 1:
Input:items = [15, 12, 10, 8, 7, 5, 3], binCapacity = 30
Output:undefined
Explanation: We need to place items sequentially:
- Bin 1: Place 15. Current sum = 15. Remaining capacity = 15.
- Bin 1: Place 12. Current sum = 27. Remaining capacity = 3.
- Item 10: Does not fit (27 + 10 = 37 > 30). Start new bin.
- Bin 2: Place 10. Current sum = 10. Remaining capacity = 20.
- Bin 2: Place 8. Current sum = 18. Remaining capacity = 12.
- Bin 2: Place 7. Current sum = 25. Remaining capacity = 5.
- Bin 2: Place 5. Current sum = 30. Remaining capacity = 0.
- Item 3: Does not fit (30 + 3 = 33 > 30). Start new bin.
- Bin 3: Place 3. Current sum = 3. Remaining capacity = 27.
All items placed. Total bins = 3.
Example 2:
Input:items = [20, 15, 15], binCapacity = 30
Output:undefined
Explanation: Items are placed sequentially:
- Bin 1: Place 20. Current sum = 20. Remaining capacity = 10.
- Item 15: Does not fit (20 + 15 = 35 > 30). Start new bin.
- Bin 2: Place 15. Current sum = 15. Remaining capacity = 15.
- Bin 2: Place 15. Current sum = 30. Remaining capacity = 0.
All items placed. Total bins = 2.
Constraints
- 1 <= items.length <= 10^5
- 1 <= items[i] <= 10^9
- 1 <= binCapacity <= 10^9
- items[i] <= binCapacity (every item must fit in a bin individually)
- `items` is sorted in descending order.
Time: O(N) Space: O(1)
The optimal approach is a greedy one: iterate through the items sequentially, maintaining a variable for the current bin's remaining capacity. If the current item fits into the current bin, add it and decrease the remaining capacity. If it doesn't fit, increment the bin count, open a new bin (resetting its remaining capacity to `binCapacity - current_item_size`), and place the item there. This method processes each item exactly once.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def min_bins(items, bin_capacity):
if not items:
return 0
num_bins = 1
current_bin_occupied = 0
for item in items:
if current_bin_occupied + item > bin_capacity:
num_bins += 1
current_bin_occupied = item
else:
current_bin_occupied += item
return num_bins
def solve():
# Read items
items_line = sys.stdin.readline().strip()
items = list(map(int, items_line.split()))
# Read binCapacity
bin_capacity = int(sys.stdin.readline().strip())
result = min_bins(items, bin_capacity)
sys.stdout.write(str(result) + "\n")
if __name__ == '__main__':
solve()