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.
https://leetcode.com/problems/minimum-cost-to-connect-sticks/
|
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 |
class Solution { public int connectSticks(int[] sticks) { //Priority Queue: sort sticks based on their length with smallest stick on the top PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer a, Integer b){ return Integer.compare(a, b); } }); //add all the sticks for(int stick: sticks){ pq.add(stick); } int cost = 0; //pull out two sticks from the priority Queue //connect them into stick and put it back in the priority queue // repeat the process till there is only one stick left in the priority queue while(pq.size()> 1){ int a = pq.poll(); int b = pq.poll(); int c = a+b; cost = cost + c; pq.offer(c); } return cost; } } |