First Fit Bin Packing

Problem

Pack items into bins of the given capacity with the first-fit heuristic and return the number of bins used.

Place each item into the first bin whose remaining capacity can hold it, otherwise open a new bin. Return 0 for non-positive capacity; items larger than the capacity still each open one bin.

Hint

First fit never revisits closed bins, so each item scans the open bins in order.

Test cases

case 1

in: [[4,8,1,4,2,1],10]

expected: 2

case 2

in: [[1,2,3,4,5],5]

expected: 4

case 3

in: [[5,5,5],5]

expected: 3

case 4

in: [[],5]

expected: 0

case 5

in: [[2,2,2,2],4]

expected: 2

Starter codePython

def first_fit_bins(items, capacity):
    # Your code here
    pass

5 test cases · run your code against them in the editor