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]);
- Finally return the answer.
- 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 the answer
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 the answer
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;
}
// print the answer
cout << "The minimum length of the wire needed is: " << min_wire(white, black, N) << endl;
return 0;
}
Output
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.
Further Readings
To learn more about C++ programming, data structures, and algorithms, you can go through the following articles.
https://www.journaldev.com/56918/0-1-knapsack-using-cpp
https://www.journaldev.com/61662/intersection-point-of-two-linked-lists-cpp
