Connect Ropes to Minimize Cost
Hard Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Connect n ropes with minimal cost, Greedy Algorithm, Priority Queue, Heap, complexity analysis, priority queue, min-heap, greedy algorithm, time complexity analysis, Heap (Priority Queue), Min-Heap, Amortized Analysis.
Problem Statement: Minimal Rope Connection Cost You are given n ropes of different lengths. Your task is to connect all ropes into a single rope with minimal total cost. The cost of connecting two ropes is equal to the sum of their lengths. You must connect the ropes in such a way that minimizes the total cumulative cost of all connection operations. Input Specification: The first line contains an integer n (1 ≤ n ≤ 10^5), the number of ropes. The second line contains n space separated integers representing the lengths of the ropes (1 ≤ length ≤ 10^4). Output Specification: Print a single integer representing the minimal total cost to connect all ropes. Constraints: 1 ≤ n ≤ 10^5 1 ≤ rope length ≤ 10^4 Sample Input 1: 4 4 3 2 6 Sample Output 1: 29 Explanation: 1. Connect ropes of lengths 2 and 3 (cost = 5). Ropes: [4, 5, 6] 2. Connect ropes of lengths 4 and 5 (cost = 9). Ropes: [9, 6] 3. Connect ropes of lengths 6 and 9 (cost = 15). Total cost = 5 + 9 + 15 = 29 Sample Input 2: 5 1 2 3 4 5 Sample Output 2: 33 Difficulty Level: Medium