# Greedy Problem Of Connecting Wires Using C++

Filed Under: C++ Today, we’ll learn to solve the greedy problem of connecting wires using C++. It is clear from the name that it’s a greedy problem. The identity of greedy problems is that you’ll always find some sort of greedy choice either by sorting or some other comparison. This problem is a must if you’re brushing up on your DSA concepts. Even if you don’t get to see this problem directly during coding competitions, there are high chances of encountering a slight variation of it. So without wasting any time, let’s get started.

## Problem Statement

There are N white dots and N black dots, all positioned on a line. You want to connect each white dot with some black dot, with a minimum total length of the wire. Find the total length of wire you need.

For example,

```position_of_white_dots = [1, 3, 4]
position_of_black_dots = [2, 5, 6]
min_length_of_wire_needed = 5

Solution:
1   2   3   4   5   6
W B  W  W  B   B
----- = 1 unit
----------- = 2 units
---------- = 2 units
```

## Approach of Solving the Greedy Problem Of Connecting Wires

The general approach to dealing with greedy problems is the following.

• Make a greedy choice.
• Verify that it’s a valid greedy choice.
• Sort the items based on greedy selection.
• Start the selection from the sorted list.

The greedy selection to solve this problem is,

Connect each white dot to its nearest unconnected black dot.

### Pseudocode

Below is the step by step process that we’ll follow to implement the algorithm.

• Greedy Choice: Match each white dot to its nearest black dot.
• Sorting such that we’re able to make the greedy choice
• sort(white.begin(), white.end());
• sort(black.begin(), black.end());
• Initialize a variable to store the answer.
• int min_dist = 0;
• Start iterating over the vectors storing the positions of white and black dots.
• for(int i = 0; i < N; i++)
• During each iteration, fulfil the greedy choice. i.e. match each white dot to its nearest black dot. Add the absolute distance between white[i] and black[i] to the answer.
• min_dist += abs(white[i] + black[i]);
• return min_dist;

## Algorithm for Solving Greedy Problem Of Connecting Wires

```int min_wire(vector <int> white, vector <int> black, int N)
{
// sort the positions of both the white
// and black dots
sort(white.begin(), white.end());
sort(black.begin(), black.end());

// now start pairing each white dot
// to the closest black dot

int min_dist = 0;
for(int i = 0; i < N; i++)
{
min_dist += abs(white[i] - black[i]);
}

return min_dist;
}
```

## Greedy Problem Of Connecting Wires Using C++ Program

```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int min_wire(vector <int> white, vector <int> black, int N)
{
// sort the positions of both the white
// and black dots
sort(white.begin(), white.end());
sort(black.begin(), black.end());

// now start pairing each white dot
// to the closest black dot

int min_dist = 0;
for(int i = 0; i < N; i++)
{
min_dist += abs(white[i] - black[i]);
}

return min_dist;
}

int main()
{
cout << "Enter the value of N" << endl;
int N;
cin >> N;

cout << "Enter the positions of white dots" << endl;
vector <int> white(N);

for(int i = 0; i < N; i++)
{
int pos;
cin >> pos;

white[i] = pos;
}

cout << "Enter the positions of black dots" << endl;
vector <int> black(N);

for(int i = 0; i < N; i++)
{
int pos;
cin >> pos;

black[i] = pos;
}

cout << "The minimum length of the wire needed is: " << min_wire(white, black, N) << endl;

return 0;
}
```

## Conclusion

In this article, we learned to solve the greedy problem of connecting wires using C++. We used the STL(Standard Template Library) sort function to sort the vectors efficiently. We also implemented a C++ program to demonstrate the working of our solution. That’s all for today, thanks for reading.