Welcome to Subscribe On Youtube
3801. Minimum Cost to Merge Sorted Lists
Description
You are given a 2D integer array lists, where each lists[i] is a non-empty array of integers sorted in non-decreasing order.
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:
len(a) + len(b) + abs(median(a) - median(b)), where len and median denote the list length and median, respectively.
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.
Return an integer denoting the minimum total cost required to merge all lists into one single sorted list.
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.
Example 1:
Input: lists = [[1,3,5],[2,4],[6,7,8]]
Output: 18
Explanation:
Merge a = [1, 3, 5] and b = [2, 4]:
len(a) = 3andlen(b) = 2median(a) = 3andmedian(b) = 2cost = len(a) + len(b) + abs(median(a) - median(b)) = 3 + 2 + abs(3 - 2) = 6
So lists becomes [[1, 2, 3, 4, 5], [6, 7, 8]].
Merge a = [1, 2, 3, 4, 5] and b = [6, 7, 8]:
len(a) = 5andlen(b) = 3median(a) = 3andmedian(b) = 7cost = len(a) + len(b) + abs(median(a) - median(b)) = 5 + 3 + abs(3 - 7) = 12
So lists becomes [[1, 2, 3, 4, 5, 6, 7, 8]], and total cost is 6 + 12 = 18.
Example 2:
Input: lists = [[1,1,5],[1,4,7,8]]
Output: 10
Explanation:
Merge a = [1, 1, 5] and b = [1, 4, 7, 8]:
len(a) = 3andlen(b) = 4median(a) = 1andmedian(b) = 4cost = len(a) + len(b) + abs(median(a) - median(b)) = 3 + 4 + abs(1 - 4) = 10
So lists becomes [[1, 1, 1, 4, 5, 7, 8]], and total cost is 10.
Example 3:
Input: lists = [[1],[3]]
Output: 4
Explanation:
Merge a = [1] and b = [3]:
len(a) = 1andlen(b) = 1median(a) = 1andmedian(b) = 3cost = len(a) + len(b) + abs(median(a) - median(b)) = 1 + 1 + abs(1 - 3) = 4
So lists becomes [[1, 3]], and total cost is 4.
Example 4:
Input: lists = [[1],[1]]
Output: 2
Explanation:
The total cost is len(a) + len(b) + abs(median(a) - median(b)) = 1 + 1 + abs(1 - 1) = 2.
Constraints:
2 <= lists.length <= 121 <= lists[i].length <= 500-109 <= lists[i][j] <= 109lists[i]is sorted in non-decreasing order.- The sum of
lists[i].lengthwill not exceed 2000.
Solutions
Solution 1
-
class Solution { public long minMergeCost(int[][] lists) { int n = lists.length; int tot = 0; for (int[] v : lists) { tot += v.length; } int[] vals = new int[tot]; int p = 0; for (int[] v : lists) { for (int x : v) { vals[p++] = x; } } Arrays.sort(vals); int m = 0; for (int i = 0; i < tot; ++i) { if (m == 0 || vals[i] != vals[m - 1]) { vals[m++] = vals[i]; } } int[] cnt = new int[1 << n]; int[] med = new int[1 << n]; for (int i = 1; i < 1 << n; ++i) { for (int j = 0; j < n; ++j) { if ((i >> j & 1) == 1) { cnt[i] += lists[j].length; } } int need = (cnt[i] + 1) / 2; int l = 0, r = m - 1; while (l < r) { int mid = (l + r) >> 1; int le = 0; for (int b = i; b > 0; b &= b - 1) { int id = Integer.numberOfTrailingZeros(b); le += upperBound(lists[id], vals[mid]); if (le >= need) { break; } } if (le >= need) { r = mid; } else { l = mid + 1; } } med[i] = vals[l]; } long[] f = new long[1 << n]; Arrays.fill(f, Long.MAX_VALUE / 4); for (int i = 1; i < 1 << n; ++i) { if (Integer.bitCount(i) == 1) { f[i] = 0; continue; } for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) { int k = i ^ j; if (j <= k) { f[i] = Math.min(f[i], f[j] + f[k] + Math.abs(med[j] - med[k])); } } f[i] += cnt[i]; } return f[(1 << n) - 1]; } private int upperBound(int[] a, int x) { int l = 0, r = a.length; while (l < r) { int mid = (l + r) >> 1; if (a[mid] <= x) { l = mid + 1; } else { r = mid; } } return l; } } -
class Solution { public: long long minMergeCost(vector<vector<int>>& lists) { int n = lists.size(); vector<int> vals; for (auto& v : lists) { vals.insert(vals.end(), v.begin(), v.end()); } sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); vector<int> cnt(1 << n); vector<int> med(1 << n); for (int i = 1; i < 1 << n; ++i) { for (int j = 0; j < n; ++j) { if (i >> j & 1) { cnt[i] += lists[j].size(); } } int need = (cnt[i] + 1) / 2; int l = 0, r = vals.size() - 1; while (l < r) { int mid = (l + r) >> 1; int le = 0; for (int b = i; b; b &= b - 1) { int id = __builtin_ctz(b); le += upper_bound(lists[id].begin(), lists[id].end(), vals[mid]) - lists[id].begin(); if (le >= need) { break; } } if (le >= need) { r = mid; } else { l = mid + 1; } } med[i] = vals[l]; } vector<long long> f(1 << n, 1e18); for (int i = 1; i < 1 << n; ++i) { if (__builtin_popcount(i) == 1) { f[i] = 0; continue; } for (int j = (i - 1) & i; j; j = (j - 1) & i) { int k = i ^ j; if (j <= k) { f[i] = min(f[i], f[j] + f[k] + abs(med[j] - med[k])); } } f[i] += cnt[i]; } return f[(1 << n) - 1]; } }; -
class Solution: def minMergeCost(self, lists: List[List[int]]) -> int: n = len(lists) vals = sorted({x for v in lists for x in v}) cnt = [0] * (1 << n) med = [0] * (1 << n) for i in range(1, 1 << n): for j, v in enumerate(lists): if i >> j & 1: cnt[i] += len(v) need = (cnt[i] + 1) // 2 l, r = 0, len(vals) - 1 while l < r: mid = (l + r) >> 1 le = 0 b = i while b: t = (b & -b).bit_length() - 1 le += bisect_right(lists[t], vals[mid]) if le >= need: break b &= b - 1 if le >= need: r = mid else: l = mid + 1 med[i] = vals[l] f = [inf] * (1 << n) for i in range(1, 1 << n): if i.bit_count() == 1: f[i] = 0 continue j = (i - 1) & i while j: k = i ^ j if j <= k: f[i] = min(f[i], f[j] + f[k] + abs(med[j] - med[k])) j = (j - 1) & i f[i] += cnt[i] return f[-1] -
func minMergeCost(lists [][]int) int64 { n := len(lists) set := map[int]struct{}{} for _, v := range lists { for _, x := range v { set[x] = struct{}{} } } vals := make([]int, 0, len(set)) for x := range set { vals = append(vals, x) } sort.Ints(vals) cnt := make([]int, 1<<n) med := make([]int, 1<<n) for i := 1; i < 1<<n; i++ { for j, v := range lists { if i>>j&1 == 1 { cnt[i] += len(v) } } need := (cnt[i] + 1) / 2 l, r := 0, len(vals)-1 for l < r { mid := (l + r) >> 1 le := 0 for b := i; b > 0; b &= b - 1 { id := bits.TrailingZeros(uint(b)) le += sort.Search(len(lists[id]), func(p int) bool { return lists[id][p] > vals[mid] }) if le >= need { break } } if le >= need { r = mid } else { l = mid + 1 } } med[i] = vals[l] } f := make([]int64, 1<<n) for i := range f { f[i] = 1e18 } for i := 1; i < 1<<n; i++ { if bits.OnesCount(uint(i)) == 1 { f[i] = 0 continue } for j := (i - 1) & i; j > 0; j = (j - 1) & i { k := i ^ j if j <= k { d := med[j] - med[k] if d < 0 { d = -d } f[i] = min(f[i], f[j]+f[k]+int64(d)) } } f[i] += int64(cnt[i]) } return f[1<<n-1] }