Join Cable Segments at the Lowest Total Splice Cost
Solve this ProblemA cable is delivered in several segments of known lengths. Two segments can be spliced into one, and a splice costs the sum of the two lengths it joins. Find the minimum total cost to splice every segment into a single cable.
The order matters: every splice creates a longer segment that will be charged again in later splices. Always splicing the two shortest segments first keeps the repeatedly-charged lengths as small as possible. A min-heap hands over the two shortest segments in O(log n) instead of re-sorting the whole pool each round.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ segments.length ≤ 50 - ◆
1 ≤ segments[i] ≤ 1000 - ◆
Splicing two segments of lengths a and b costs a + b and produces one segment of length a + b - ◆
Splice until a single cable remains; return the minimum total cost (0 if there is only one segment to begin with)
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 Splice
BruteThe cheapest way to finish is always to splice the two shortest segments first (their cost is paid once now, then again for every later splice that uses the result, so the shortest pieces should be buried deepest). Keep the segments in a plain list; each round sort the whole list, remove the two smallest, add their sum back, and add that sum to the total. It is right, but it pays for a full sort in each of the n − 1 rounds.
O(n² log n)O(n)1class Solution {
2 public int minSpliceCost(int[] segments) {
3 List<Integer> pool = new ArrayList<>();
4 for (int length : segments) pool.add(length);
5 int total = 0;
6 while (pool.size() > 1) {
7 Collections.sort(pool);
8 int joined = pool.get(0) + pool.get(1);
9 pool.remove(0);
10 pool.remove(0);
11 pool.add(joined);
12 total += joined;
13 }
14 return total;
15 }
16}Optimal — Min-Heap Pops the Two Shortest
OptimalThe same greedy rule, but the pool lives in a min-heap so the two shortest segments are always at hand. Each round pops two segments, pushes their joined segment back, and adds the joined length to the total. Popping and pushing each cost O(log n), so all n − 1 splices cost O(n log n) instead of re-sorting the whole pool every round.
O(n log n)O(n)1class Solution {
2 public int minSpliceCost(int[] segments) {
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int length : segments) heap.offer(length);
5 int total = 0;
6 while (heap.size() > 1) {
7 int joined = heap.poll() + heap.poll();
8 total += joined;
9 heap.offer(joined);
10 }
11 return total;
12 }
13}