564. Rope Joiner
A rigging crew keeps n loose rope pieces, where ropes[i] is the length of piece i. Two pieces can be spliced into one longer piece, and a splice costs exactly the sum of the two lengths being joined. The crew must keep splicing until only a single piece is left.
Return the minimum possible total splicing cost to turn all the pieces into one. If there is only one piece to begin with, no splice is needed and the answer is 0. The result can exceed the 32-bit range, so it is returned as a 64-bit integer.
Aim for O(n log n) time and O(n) extra space.
Example 1
- Input:
- ropes = [7,1,5,2]
- Output:
- 26
- Explanation:
Join 1+2 (cost 3), then 3+5 (cost 8), then 7+8 (cost 15): total 26.
Example 2
- Input:
- ropes = [10,10,10]
- Output:
- 50
- Explanation:
Join 10+10 (cost 20), then 20+10 (cost 30): total 50.
Example 3
- Input:
- ropes = [9]
- Output:
- 0
- Explanation:
A single piece needs no splicing, so the cost is 0.
Constraints
1 ≤ ropes.length ≤ 1000001 ≤ ropes[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)