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

Challenge: Connecting n Pipes with Minimum Cost

Explore how to apply greedy algorithm techniques to connect multiple pipes with different lengths at the minimum total cost. Learn to design a step-by-step solution that prioritizes combining the shortest pipes first, reducing the overall connection expense.

We'll cover the following...

Problem statement

Implement a function that connects nn pipes of different lengths into one pipe. Assume that the cost to connect two pipes is equal to the sum of their lengths. We need to connect the pipes at a minimum cost.

Input

An array containing lengths of nn pipes.

Output

The total cost of connecting the pipes.

Sample input

pipes = {4, 3, 2, 6};

Sample output

result = 29;
canvasAnimation-image
1 / 4

Coding exercise

First, take a close look at this problem and design a step-by-step algorithm before jumping to the implementation. This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the solution provided in the solution section. Good luck!

C# 9.0
using System;
using System.Collections.Generic;
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)
    {
        // Write your code here!
        return 0;
    }
}
public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> data;
    public PriorityQueue()
    {
        this.data = new List<T>();
    }
    public void Enqueue(T item)
    {
        data.Add(item);
        int ci = data.Count - 1; // child index; start at end
        while (ci > 0)
        {
            int pi = (ci - 1) / 2; // parent index
            if (data[ci].CompareTo(data[pi]) >= 0) break; // child item is larger than (or equal) parent so we're done
            T tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp;
            ci = pi;
        }
    }
    public T Dequeue()
    {
        // assumes pq is not empty; up to calling code
        int li = data.Count - 1; // last index (before removal)
        T frontItem = data[0];   // fetch the front
        data[0] = data[li];
        data.RemoveAt(li);
        --li; // last index (after removal)
        int pi = 0; // parent index. start at front of pq
        while (true)
        {
            int ci = pi * 2 + 1; // left child index of parent
            if (ci > li) break;  // no children so done
            int rc = ci + 1;     // right child
            if (rc <= li && data[rc].CompareTo(data[ci]) < 0) // if there is a right child (rc <= li) and it is smaller than left child, use the right child instead
                ci = rc;
            if (data[pi].CompareTo(data[ci]) <= 0) break; // parent is smaller than (or equal to) smallest child so done
            T tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp; // swap parent and child
            pi = ci;
        }
        return frontItem;
    }
    public int Count
    {
        get { return data.Count; }
    }
    public override string ToString()
    {
        return string.Join(", ", data);
    }
}