1889. Minimum Space Wasted From Packaging Hard

1/**
2 * [1889] Minimum Space Wasted From Packaging
3 *
4 * You have n packages that you are trying to place in boxes, one package in each box. There are m suppliers that each produce boxes of different sizes (with infinite supply). A package can be placed in a box if the size of the package is less than or equal to the size of the box.
5 * The package sizes are given as an integer array packages, where packages[i] is the size of the i^th package. The suppliers are given as a 2D integer array boxes, where boxes[j] is an array of box sizes that the j^th supplier produces.
6 * You want to choose a single supplier and use boxes from them such that the total wasted space is minimized. For each package in a box, we define the space wasted to be size of the box - size of the package. The total wasted space is the sum of the space wasted in all the boxes.
7 * 
8 * 	For example, if you have to fit packages with sizes [2,3,5] and the supplier offers boxes of sizes [4,8], you can fit the packages of size-2 and size-3 into two boxes of size-4 and the package with size-5 into a box of size-8. This would result in a waste of (4-2) + (4-3) + (8-5) = 6.
9 * 
10 * Return the minimum total wasted space by choosing the box supplier optimally, or -1 if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 10^9 + 7.
11 *  
12 * Example 1:
13 * 
14 * Input: packages = [2,3,5], boxes = [[4,8],[2,8]]
15 * Output: 6
16 * Explanation: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
17 * The total waste is (4-2) + (4-3) + (8-5) = 6.
18 * 
19 * Example 2:
20 * 
21 * Input: packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
22 * Output: -1
23 * Explanation: There is no box that the package of size 5 can fit in.
24 * 
25 * Example 3:
26 * 
27 * Input: packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
28 * Output: 9
29 * Explanation: It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
30 * The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	n == packages.length
36 * 	m == boxes.length
37 * 	1 <= n <= 10^5
38 * 	1 <= m <= 10^5
39 * 	1 <= packages[i] <= 10^5
40 * 	1 <= boxes[j].length <= 10^5
41 * 	1 <= boxes[j][k] <= 10^5
42 * 	sum(boxes[j].length) <= 10^5
43 * 	The elements in boxes[j] are distinct.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/minimum-space-wasted-from-packaging/
49// discuss: https://leetcode.com/problems/minimum-space-wasted-from-packaging/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn min_wasted_space(packages: Vec<i32>, boxes: Vec<Vec<i32>>) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_1889() {
67    }
68}
69