Merge Files K at a Time at the Lowest Total Cost
Solve this ProblemA backup tool can merge between 2 and k files into one file in a single step. Merging costs the total size of the files it combines, and the result is one file of that size. Given the sizes of the files, find the minimum total cost to end up with a single file.
Just as with pairwise merging, the smallest files should be merged first because every merged file is charged again in later merges. The wrinkle is the number of files: if a full k-way merge can't finish the job exactly, one merge must be smaller. Padding the heap with zero-size files makes every merge a clean k-way merge without changing the cost.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ files.length ≤ 40, 2 ≤ k ≤ 6 - ◆
1 ≤ files[i] ≤ 500 - ◆
One merge combines between 2 and k files into a single file whose size is their total; the merge costs that total size - ◆
Merge until one file remains; return the minimum total cost (0 if there is already one file)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Re-Sort the Pool Before Every Merge
BruteUse the same greedy idea as for pairwise merging: always merge the smallest files together, because every merged file is charged again in later merges. With merges of up to k files, the only subtlety is the first merge: if (n − 1) is not a multiple of (k − 1) then some merge has to be smaller than k, and the cheapest place for that smaller merge is the very first one, over the r + 1 smallest files where r = (n − 1) mod (k − 1). After that every merge takes exactly k files. Each round sorts the whole pool from scratch to find the smallest files.
O(n² log n)O(n)1class Solution {
2 public int minMergeCost(int[] files, int k) {
3 List<Integer> pool = new ArrayList<>();
4 for (int size : files) pool.add(size);
5 int r = (pool.size() - 1) % (k - 1);
6 int group = (r == 0) ? k : r + 1;
7 int total = 0;
8 while (pool.size() > 1) {
9 Collections.sort(pool);
10 int merged = 0;
11 for (int i = 0; i < group; i++) merged += pool.remove(0);
12 pool.add(merged);
13 total += merged;
14 group = k;
15 }
16 return total;
17 }
18}Optimal — Zero-Size Padding With a Min-Heap
OptimalThe "smaller first merge" can be handled elegantly: add just enough phantom zero-size files so that (size − 1) is a multiple of (k − 1). Zero-size files cost nothing to merge, and now every merge takes exactly k files and the process ends with exactly one. Load everything into a min-heap; each round pops the k smallest, merges them, pays their total, and pushes the result back. Every pop and push is O(log n), so no round ever sorts the pool.
O(n log n)O(n)1class Solution {
2 public int minMergeCost(int[] files, int k) {
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int size : files) heap.offer(size);
5 while ((heap.size() - 1) % (k - 1) != 0) heap.offer(0);
6 int total = 0;
7 while (heap.size() > 1) {
8 int merged = 0;
9 for (int i = 0; i < k; i++) merged += heap.poll();
10 total += merged;
11 heap.offer(merged);
12 }
13 return total;
14 }
15}