Where it runs
1. The problem
A log-compaction job keeps sorted segments lined up in a row. It merges them two at a time until one is left. Merging two segments costs the sum of their sizes, because every record of both has to be read and written again. There is a rule: you can only merge segments that sit next to each other, and their order must stay the same.
The order you pick changes the total cost. Merge the wrong pair first, and a big segment later goes through extra merges. Given the segment sizes, you want the cheapest total cost to combine them all into one.
The first idea is to always merge the neighbouring pair with the smallest sum. Here that rule sometimes loses. Take the sizes [3, 3, 2, 4]. The lightest pair is 3 and 2 (sum 5). That leaves [3, 5, 4], then 3 + 5 = 8, and at the end 12. Total: 5 + 8 + 12 = 25. Start with 3 + 3 = 6 instead, then merge 2 + 4 = 6, and finish with 6 + 6 = 12: the total is 24. So the greedy rule doesn't work here.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedminMergeCost([4, 1, 3, 2])| j=0 | j=1 | j=2 | j=3 | |
|---|---|---|---|---|
| i=0 | 0 | |||
| i=1 | 0 | |||
| i=2 | 0 | |||
| i=3 | 0 |
Merge neighbouring piles until one is left. Each merge costs the total size of the two piles it joins. Find the cheapest order.
Recognise it
Say these words and it is this pattern
- combine adjacent pieces at some cost
- best way to split a range into two parts
- matrix chain multiplication order
- merge cost depends on the whole span
- optimal parenthesization or build order
Looks similar, isn't
- Dynamic programming (1-D)
One index describes a prefix. A range needs both of its ends.
- DP on subsequences (LIS / LCS / edit distance)
There the two indices point into two different sequences. Here both sit in one.
- DP on trees
A tree splits at its children, which are given. An interval splits at a point you choose.
- Greedy (exchange argument)
Greedy would pick an order and commit to it. Here every split point has to be tried.
n up to about 500 gives O(n cubed). There are n squared ranges, each with n split points.
On LeetCode
Problems where you merge, cut or burst a row in some order and the order changes the cost. For the range i to j try every split point k, add the two halves and the cost of this step, and fill the table by range length.
Add 0 and n to the sorted cuts. Each cut costs the length of the piece it lands in, and the table runs over ranges between cuts.
For the side from i to j try every vertex k between them as the third corner of a triangle, and add the two smaller polygons.
Choose k as the balloon in i to j that bursts last, so its neighbours at that moment are i minus 1 and j plus 1.
With k equal to 2 this is the lesson task. A larger k adds a check that n minus 1 divides by k minus 1, and a range merges into one pile only when its length allows it.