Problem statement

https://binarysearch.com/problems/Fruit-Basket-Packing/

Solution

A bit strange problem in my opinion. What we need to do here is to simulate process, but we need to follow order. So, for each cost, size, cnt in fruits, we first find all full baskets avaliable and keep them in form (size, cost, number of such baskets). Similar logic is for not full baskets, we can have only 1 of them. Then we sort all candidates in correct order and use greedy strategy.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, fruits, k, s):
        baskets, ans = [], 0

        for cost, size, cnt in fruits:
            if size > s: continue
            x, _ = divmod(s, size)
            f, r = divmod(cnt, x)
            if x: baskets.append((x * size, x * cost, f))
            if r: baskets.append((r * size, r * cost, 1))

        for _, b_cst, b_aval in sorted(baskets, key=lambda b: (-b[0], b[1])):
            if k == 0: break
            taken = min(k, b_aval)
            ans += taken * b_cst
            k -= taken

        return ans