-
Notifications
You must be signed in to change notification settings - Fork 2
/
MinimumCostToConnectSticks.java
67 lines (60 loc) · 2.14 KB
/
MinimumCostToConnectSticks.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package Leetcode;
import java.util.PriorityQueue;
/**
* @author kalpak
*
* You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.
*
* You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect all the sticks until there is only one stick remaining.
*
* Return the minimum cost of connecting all the given sticks into one stick in this way.
*
*
*
* Example 1:
* Input: sticks = [2,4,3]
* Output: 14
* Explanation: You start with sticks = [2,4,3].
* 1. Combine sticks 2 and 3 for a cost of 2 + 3 = 5. Now you have sticks = [5,4].
* 2. Combine sticks 5 and 4 for a cost of 5 + 4 = 9. Now you have sticks = [9].
* There is only one stick left, so you are done. The total cost is 5 + 9 = 14.
*
* Example 2:
* Input: sticks = [1,8,3,5]
* Output: 30
* Explanation: You start with sticks = [1,8,3,5].
* 1. Combine sticks 1 and 3 for a cost of 1 + 3 = 4. Now you have sticks = [4,8,5].
* 2. Combine sticks 4 and 5 for a cost of 4 + 5 = 9. Now you have sticks = [9,8].
* 3. Combine sticks 9 and 8 for a cost of 9 + 8 = 17. Now you have sticks = [17].
* There is only one stick left, so you are done. The total cost is 4 + 9 + 17 = 30.
*
* Example 3:
* Input: sticks = [5]
* Output: 0
* Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.
*
* Constraints:
*
* 1 <= sticks.length <= 104
* 1 <= sticks[i] <= 104
*/
public class MinimumCostToConnectSticks {
public static int connectSticks(int[] sticks) {
int result = 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int stick : sticks)
minHeap.offer(stick);
while (minHeap.size() >= 2) {
int cost = minHeap.poll() + minHeap.poll();
result += cost;
minHeap.offer(cost);
}
return result;
}
public static void main(String[] args) {
int[] arr = new int[]{2,4,3};
System.out.println(connectSticks(arr));
arr = new int[]{5};
System.out.println(connectSticks(arr));
}
}