3801. Minimum Cost to Merge Sorted Lists Hard

1/**
2 * [3801] Minimum Cost to Merge Sorted Lists
3 *
4 * You are given a 2D integer array lists, where each lists[i] is a non-empty array of integers sorted in non-decreasing order.
5 * You may repeatedly choose two lists a = lists[i] and b = lists[j], where i != j, and merge them. The cost to merge a and b is:
6 * len(a) + len(b) + abs(median(a) - median(b)), where len and median denote the list length and median, respectively.
7 * After merging a and b, remove both a and b from lists and insert the new merged sorted list in any position. Repeat merges until only one list remains.
8 * Return an integer denoting the minimum total cost required to merge all lists into one single sorted list.
9 * The median of an array is the middle element after sorting it in non-decreasing order. If the array has an even number of elements, the median is the left middle element.
10 *  
11 * <strong class="example">Example 1:
12 * <div class="example-block">
13 * Input: <span class="example-io">lists = [[1,3,5],[2,4],[6,7,8]]</span>
14 * Output: <span class="example-io">18</span>
15 * Explanation:
16 * Merge a = [1, 3, 5] and b = [2, 4]:
17 * 
18 * 	len(a) = 3 and len(b) = 2
19 * 	median(a) = 3 and median(b) = 2
20 * 	cost = len(a) + len(b) + abs(median(a) - median(b)) = 3 + 2 + abs(3 - 2) = 6
21 * 
22 * So lists becomes [[1, 2, 3, 4, 5], [6, 7, 8]].
23 * Merge a = [1, 2, 3, 4, 5] and b = [6, 7, 8]:
24 * 
25 * 	len(a) = 5 and len(b) = 3
26 * 	median(a) = 3 and median(b) = 7
27 * 	cost = len(a) + len(b) + abs(median(a) - median(b)) = 5 + 3 + abs(3 - 7) = 12
28 * 
29 * So lists becomes [[1, 2, 3, 4, 5, 6, 7, 8]], and total cost is 6 + 12 = 18.
30 * </div>
31 * <strong class="example">Example 2:
32 * <div class="example-block">
33 * Input: <span class="example-io">lists = [[1,1,5],[1,4,7,8]]</span>
34 * Output: <span class="example-io">10</span>
35 * Explanation:
36 * Merge a = [1, 1, 5] and b = [1, 4, 7, 8]:
37 * 
38 * 	len(a) = 3 and len(b) = 4
39 * 	median(a) = 1 and median(b) = 4
40 * 	cost = len(a) + len(b) + abs(median(a) - median(b)) = 3 + 4 + abs(1 - 4) = 10
41 * 
42 * So lists becomes [[1, 1, 1, 4, 5, 7, 8]], and total cost is 10.
43 * </div>
44 * <strong class="example">Example 3:
45 * <div class="example-block">
46 * Input: <span class="example-io">lists = [[1],[3]]</span>
47 * Output: <span class="example-io">4</span>
48 * Explanation:
49 * Merge a = [1] and b = [3]:
50 * 
51 * 	len(a) = 1 and len(b) = 1
52 * 	median(a) = 1 and median(b) = 3
53 * 	cost = len(a) + len(b) + abs(median(a) - median(b)) = 1 + 1 + abs(1 - 3) = 4
54 * 
55 * So lists becomes [[1, 3]], and total cost is 4.
56 * </div>
57 * <strong class="example">Example 4:
58 * <div class="example-block">
59 * Input: <span class="example-io">lists = [[1],[1]]</span>
60 * Output: <span class="example-io">2</span>
61 * Explanation:
62 * The total cost is len(a) + len(b) + abs(median(a) - median(b)) = 1 + 1 + abs(1 - 1) = 2.
63 * </div>
64 *  
65 * Constraints:
66 * 
67 * 	2 <= lists.length <= 12
68 * 	1 <= lists[i].length <= 500
69 * 	-10^9 <= lists[i][j] <= 10^9
70 * 	lists[i] is sorted in non-decreasing order.
71 * 	The sum of lists[i].length will not exceed 2000.
72 * 
73 */
74pub struct Solution {}
75
76// problem: https://leetcode.com/problems/minimum-cost-to-merge-sorted-lists/
77// discuss: https://leetcode.com/problems/minimum-cost-to-merge-sorted-lists/discuss/?currentPage=1&orderBy=most_votes&query=
78
79// submission codes start here
80
81impl Solution {
82    pub fn min_merge_cost(lists: Vec<Vec<i32>>) -> i64 {
83        
84    }
85}
86
87// submission codes end
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92
93    #[test]
94    fn test_3801() {
95    }
96}
97