instagram

Join ropes in such a way that the cost is minimum.

Given N ropes of lengths L1, L2, L3, L4, …, LN. I had to join every rope to get a final rope of length L1 + L2 + … + LN.
However, I can join only two ropes at a time and the cost of joining the two ropes is L1 + L2. I was supposed to join ropes in such a way that the cost is minimum.

package com.omt.learn.algo;

import java.util.PriorityQueue;

public class JoinTheRope {

	public static void main(String[] args) {
		int a[] = { 2, 34, 6, 3, 12, 87, 78, 5, 33, 42, 6, 1, 3, 2, 4, 6, 8, 2, 1 };
		joinRope(a);
	}

	public static void joinRope(int a[]) {

		PriorityQueue<Integer> p = new PriorityQueue<>();

		for (int i : a) {
			p.add(i);
		}

		while (p.size() > 1) {
			p.add(p.poll() + p.poll());
		}

		System.out.println(p.poll());

	}

}
Share