Where it runs
1. The problem
Until now the greedy algorithms chose in an order known in advance. Interval scheduling sorted the requests once by end time and then walked the list; the exchange argument showed that one sort was enough. Here the order keeps changing. You combine items, and each combination creates a new item that has to be compared with everything left. The two smallest values you need for the next step change after every move, so one sort at the start cannot give them to you.
The concrete task. You have several files of sizes [1, 2, 3, 4] to merge into one. You can merge only two files at a time, and a merge costs as much work as the two files weigh together. The merged file goes back into the set and may be merged again. You want the smallest total cost of all the merges that leave one file.
The order of the merges changes the total. Merge 1+2=3 (cost 3), then 3+3=6 (cost 6), then 4+6=10 (cost 10): total 19. If you always take the two biggest files, you get 4+3=7, 7+2=9, 9+1=10, total 7 + 9 + 10 = 26. The small files then end up inside big merges again and again, and the total grows.
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 includedOn LeetCode
Problems that keep taking the two smallest or two largest values, combine them and put the result back. A heap gives you both values in O(log n) each round. The lesson's exact task is Minimum Cost to Connect Sticks (1167), which is premium on LeetCode.
Pop the two smallest, push the smaller times 2 plus the larger, and count rounds until the smallest reaches k. It is the lesson's loop with another merge formula.
The same loop with a max-heap. Smash the two heaviest stones and push back the difference when it is above zero.
Each second fill one cup of each of the two types with the most left, so pop the two largest counts, lower each by one and push them back.