Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Connecting n Pipes with Minimum Cost

Explore how to apply greedy algorithms and priority queues to efficiently connect pipes at minimal cost. Understand the iterative process of selecting the smallest pipes and combining their lengths while managing complexity with O(n log n) operations.

We'll cover the following...

Solution: Sorting

MinCost
PriorityQueue
class Program
{
    /// <summary>
    /// Calculates the minimum cost of connecting pipes.
    /// </summary>
    /// <param name="pipes">An array where its length is the number of pipes and indexes are the specific lengths of the pipes.</param>
    /// <returns>The minimum cost of connecting the pipes.</returns>
    public static int MinCost(int[] pipes)
    {
        // Create a priority queue out of the given list
        PriorityQueue<int> pq = new PriorityQueue<int>();
        foreach (int pipe in pipes)
        {
            pq.Enqueue(pipe);
        }
        // Initialize result
        int cost = 0;
        // While size of priority queue is more than 1
        while (pq.Count > 1)
        {
            // Extract shortest two pipes from the priority queue
            int first = pq.Dequeue();
            int second = pq.Dequeue();
            // Connect the pipe: update cost and insert the new pipe to pipes queue
            cost += first + second;
            pq.Enqueue(first + second);
        }
        return cost;
    }
    // Main program to test the above function
    public static void Main(string[] args)
    {
        int[] pipes = new int[] { 4, 3, 2, 6 };
        Console.WriteLine(MinCost(pipes)); // Output: 29
    }
}

Explanation

If you look at the animation presented in the previous lesson, you will notice that the lengths of the pipes that are picked first are included iteratively (i.e., each time). Therefore, we want them to be as small as possible. Now, let’s be greedy!

First, we initialize the priority queue with the pipes. The priority queue ensures that the two smallest length pipes are selected in every iteration. In this way, in every iteration, the previous cost (which is the length of the last two pipes connected) is added to the cost of connected pipes in this iteration until all pipes are connected.

Time complexity

The time complexity for this solution is O(nlog⁡n)O(n \log n) because both the push and pop operations of the priority queue take O(log⁡n)O(\log n) time.