You are given an integer array Inventories representing the ribbon inventories, where Inventories[i] represents the length of the ith ribbon, and an array of orders.
Each order in orders is an array of integers, representing the ribbons needed with certain lengths for that order. For example, if order = [1,2], then that means this order need a ribbon with length 1 and a ribbon with length 2.
You may cut any of the ribbons in the inventory into any number of segments of positive integer lengths, or perform no cuts at all.
However, you cannot combine two ribbons in the inventory to form a longer ribbon and fullfil an order. Each segment/ribbon in the inventory cannot be reused. The question is, what is the maximum number of orders that can be fulfilled?
Example 1:
Input: Inventories = [1,8,7], orders = [[1, 2], [4, 3, 6]]
Output: 2
Explanation:
First cut inventories[1] into [2,6], then the inventory becomes [1, 7, 2, 6]. Use inventories[0] and inventories[2] for the first order. The rest of the inventories are [7,6], then cut the ribbon with the length of 7 into 4 and 3 to fulfill the second order. So in total 2 orders are fulfilled.
Example 2:
Input: Inventories = [1,2,3], orders = [[3, 3], [4]]
Output: 0
Explanation:
None of the orders can be fulfilled. Notice we cannot combine inventories[0] and inventories[1] for orders[0].
Example 3:
Input: Inventories = [3], orders = [[2]]
Output: 1
Explanation:
Cut the ribbon into 2 and 1, and use the first segment for that order.
I have been breaking my head over this, I thought of some greedy approaches, sorting orders by the max ribbon required by each item and processing it. Eg: [[4,3,6], [1,2]] becomes [[1,2],[4,3,6]]. But this fails when order max is less but the number of items in the order is huge.
Does anyone have any approach ?
