Minimum Cost of ropes geeks solution

Minimum Cost of ropes geeks solution

  October 18, 2017    

---

Problem:

There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.


idea is to use priorityQ so that we can get minimum every time and add it ,again push result into Q until only 1 element left in q.

Code:

public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
    for(int i=0;i<n;++i)
    pq.add(ab.nextInt());
    int s=0;
    while(pq.size()>=2 )
    {
        int x=pq.poll();
        int y=pq.poll();
        pq.add(x+y);
        s+=(x+y);
    }
    System.out.println(s);
}
}