Expert · Greedy algorithms · 248 of 264
Joining ropes
Joining two ropes costs the sum of their lengths. Join all the ropes into one as cheaply as possible: always join the two shortest (use heapq).
Input: the rope lengths on one line. Output: the smallest total cost.
Examples
Input
4 3 2 6
Output
29
Input
5
Output
0
Input
1 1 1 1
Output
8
One more test checks other inputs when you press Check.
Stuck? The idea behind greedy algorithms
Take the best-looking choice at each step and never go back: sorting first usually makes the best choice obvious.
It works only when a local best choice can't spoil the whole answer; for meetings, choosing the one that ends earliest leaves the most room.
meetings = [(1, 4), (3, 5), (0, 6), (5, 7)]
end, count = -1, 0
for s, e in sorted(meetings, key=lambda m: m[1]):
if s >= end:
count += 1
end = e
print(count)Watch for: Sorting by the wrong thing (start instead of end) gives a plausible but wrong answer: try a small case by hand.