Greedy Problem Of Connecting Wires Using C++

Filed Under: C++
Greedy Problem Of Connecting Wires Using 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
Example 1
Example

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;
}
Program Code 2
Connecting Wires Using C++ Code

Output

Connecting Wires Output
Connecting Wires Using C++ 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

close
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors