Fewest Crates for the Harvest

Easy

After the harvest the apples sit in baskets: basket i holds baskets[i] apples. The warehouse has crates, and crate j fits up to crates[j] apples. All the apples have to be moved into crates. Apples from one basket may be split across several crates. Return the smallest number of crates that is enough. The crates together are guaranteed to be large enough.

Example 1

baskets=[6, 2, 7], crates=[5, 9, 3, 8] → 2

There are 15 apples. The two largest crates hold 9 + 8 = 17 ≥ 15, and no single crate fits 15, so the answer is 2.

Example 2

baskets=[4, 4], crates=[3, 3, 3] → 3

8 apples, while two crates hold only 6, so all three are needed.

Example 3

baskets=[1, 1, 1], crates=[10, 2] → 1

Constraints

1 ≤ len(baskets), len(crates) ≤ 50
1 ≤ baskets[i], crates[j] ≤ 50
sum(crates) ≥ sum(baskets)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Cake Slices for Guests Easy Strength of the Weaker Partner Easy Triangle From Sticks Easy Sign Flips for the Largest Sum Easy Pack the Backpack Easy

Input

baskets=[6, 2, 7], crates=[5, 9, 3, 8]

Expected

Run checks the first 3 tests in your browser. Submit checks all 77 tests on the server, hidden ones included.