items, each into its own crate. An item fits into a crate when its size is at most the crate's size.
All crates must come from one supplier. suppliers[j] lists the crate sizes supplier j makes, and each size is available in unlimited quantity. The wasted space in a crate is the crate size minus the size of the item inside, and the total waste is the sum over all crates.
Pick the supplier and the crates so that the total waste is as small as possible, and return it modulo 10⁹ + 7. If no supplier can pack every item, return -1.items=[1, 4, 6, 7], suppliers=[[5, 10], [7, 2], [8]] → 5
Supplier one: 1 and 4 go into size-5 crates, 6 and 7 into size-10 crates, wasting (5−1)+(5−4)+(10−6)+(10−7) = 12. Supplier two: 1 into a size-2 crate and the rest into size-7 crates, wasting 1+3+1+0 = 5. Supplier three: everything into size-8 crates, wasting 7+4+2+1 = 14. The best is 5.
items=[3, 9], suppliers=[[4, 8], [2]] → -1
No supplier has a crate that holds the size-9 item, so the answer is -1.
items=[2, 2, 2], suppliers=[[3], [2, 6]] → 0
items=[1, 4, 6, 7], suppliers=[[5, 10], [7, 2], [8]]
5
Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.