CC-12 : Find minimum cost to join N ropes.

Description:

Given an array, find the cost of joining the ropes given in the input array, where value each index of array represents the length of the rope. To join 2 ropes the cost is same as the length of the ropes. So, if we join 3 ropes, the cost of joining them is as follows:

Step1 : Join rope1 + rope2, cost of joining: (r1.length + r2.length) and total cost : (r1.length + r2.length).

Step2: Join rope3 to above, cost of current joining (r1.length + r2.length+r3 length) and total cost combing step1 and step2 : (r1.length + r2.length)+ (r1.length + r2.length+r3 length).

And so on…

Test cases and expected outputs:

Input Parameters	Expected outputs
Rope joining costs : 4,3,1,2	Minimum cost: 19

Pseudocode:

This method takes integer array named ropeLengths containing rope lengths as input parameter.

Initialize a PriorityQueue instance named minHeap to be used as Min Heap.

Iterate though ropeLengthsfrom index 0 to index heap1.length-1:

Add ropeLengths [idx]to minHeap.

Initialize variable totalCost to 0.

While (minHeap.size() > 1) :

Extract firstRopeCost from top of minHeap.

Extract secondRopeCost from top of minHeap.

Calculate joincost as firstRopeCost+ secondRopeCost.

Calculate totalCost= totalCost+joinCost.

Add joinCost bak to minHeap.

Return totalCost.

Code:

public int minimumCostToConnectNRopes(int[] ropeLengths) {
	
	PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>();
	for (int idx=0; idx < ropeLengths.length; idx++) {
		minHeap.add(ropeLengths[idx]);
	}
	int totalCost=0;
	while (minHeap.size() >1 ) {
		int firstRopeCost=minHeap.remove();
		int secondRopeCost=minHeap.remove();
		int joinCost=firstRopeCost+secondRopeCost;
		totalCost+=joinCost;
		minHeap.add(joinCost);
	}	
	return totalCost;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.PriorityQueue;

public class HeapMinimumCostToConnectNRopes {
	
public int minimumCostToConnectNRopes(int[] ropeLengths) {
	
	PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>();
	for (int idx=0; idx < ropeLengths.length; idx++) {
		minHeap.add(ropeLengths[idx]);
	}
	int totalCost=0;
	while (minHeap.size() >1 ) {
		int firstRopeCost=minHeap.remove();
		int secondRopeCost=minHeap.remove();
		int joinCost=firstRopeCost+secondRopeCost;
		totalCost+=joinCost;
		minHeap.add(joinCost);
	}	
	return totalCost;
}

public static void printArraySummary(int[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex < intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println(" ************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below
	 **********************/
	int retVal;
	try {
	HeapMinimumCostToConnectNRopes hp=new HeapMinimumCostToConnectNRopes();
	int[] nums= {4,3,1,2};
	printArraySummary(nums, "Rope joining costs");
	retVal=hp.minimumCostToConnectNRopes(nums);
	System.out.print("Minimum cost: "+ retVal);
		
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
		
}
}