1167. Minimum Cost to Connect Sticks

T: O(nlogn)
S: O(n)

class Solution {
    public int connectSticks(int[] sticks) {
        int n = sticks.length;
        if (n == 1 || n == 0) {
            return 0;
        }
        Queue<Integer> pq = new PriorityQueue<>();
        
        for (int i = 0; i < n; i++) {
            pq.offer(sticks[i]);
        }
        
        int cost = 0;
        while (!pq.isEmpty()) {
            int num = 0;
            if (!pq.isEmpty()) {
                num = pq.poll();
            }
            int num2 = 0;
            if (!pq.isEmpty()) {
                num2 = pq.poll();
            }
            int newCost = num + num2;
            cost += newCost;
            pq.offer(newCost);
            if (pq.size() == 1) {
                break;
            }
        }
        
        return cost;
    }
}

/*
[1,8,3,5]

1 3

greedy thinking + pq

一定從小的來接, cost 最小,
所以可以用一個 pq, 來放值
然後加完後的 cost 再丟回去 pq
依照這版邏輯, 最後 pq 會剩下只有一個結果（cost) 時要跳出

T: O(nlogn)
S: O(n)
*/

more simpler

change to

while (pq.size() > 1) {

then don't need worry about pq.poll is empty()

class Solution {
    public int connectSticks(int[] sticks) {
        int n = sticks.length;
        if (n == 1 || n == 0) {
            return 0;
        }
        Queue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            pq.offer(sticks[i]);
        }
        
        int cost = 0;
        while (pq.size() > 1) {
            int newCost = pq.poll() + pq.poll();
            cost += newCost;
            pq.offer(newCost);
        }
        
        return cost;
    }
}