Intro to Greedy Algorithms with C++

A greedy algorithm is a simple and efficient algorithmic approach for solving any given problem by selecting the best available option at that moment of time, without bothering about the future results.

10 min readJan 29, 2021

In simple words, here, it is believed that the locally best choices made would be leading towards globally best results.
In this approach, we never go back to reverse the decision of selection made which is why this algorithm works in a top-bottom manner.

Advantages of Greedy Approach:

It is easier to describe.
It can perform better in most of the scenarios than other algorithms.

NOTE: We have mentioned “in most of the scenarios” in the earlier point because in some cases, this approach doesn’t always produce correct results due to the nature of not reversing the decision made.
This is why we opt for Dynamic Programming strategy in such scenarios.

Greedy Algorithm Examples

Let us see with the help of below examples about how greedy algorithm can be used to find optimal solutions.

Path Finder Problem

Case Study:

Consider you want to visit a restaurant (point B) in your car from your home (Point A) and there are 20 possible ‘paths’ or ‘routes’. The paths are composed of many roads — each adjacent to the other. Imagine that upon leaving your home, you would encounter many junctions since we have many roads splitting at many points.

Let us assume that these junctions don’t have markers which shows the remaining distance to restaurant. Instead of that, we know the length of all the individual roads from here. To make things simpler, assume that you know these lengths before you are leaving from your home. Naturally you would want to reach the restaurant using minimum fuel and as early as possible. Right?

So, if you choose to minimize cost of the fuel, it would be same as taking paths of minimum length. Now, how should we proceed?

Analysis:

The simplest and the most obvious method is to compute all path lengths at home, and choose the one with minimum value. This is called brute force.
The problem with such solutions is you have to waste a lot of your time and rough-sheets calculating what path has minimum lengths and you would need a calculator too.
It may not be a mighty task with 20 roads, but if you’d 20000 it won’t be simple anymore. Can you imagine yourself calculating the distance when you are starving? We surely can’t think when hungry! :D
Now let’s try to solve things in easier manner. Leave home without performing any calculations. When you encounter a junction with several roads, what would be your natural instinct?
Say you see 5 roads of length 1,4,20,100 and 200- which one would you choose?
Unless you apply algorithms at every point of your life, you would instinctively choose the road of length 1.
If you had been able to calculate using the minimum distance remaining to restaurant along this path (which unfortunately you don’t know yet), you would have chosen the optimal path.
However, by choosing the path which at the moment seemed best you chose a suboptimal path hoping that this would help u minimize fuel in the overall run.
If you apply the same intuition and logic at every junction, computer scientists would declare that you have used Greedy Algorithm successfully to reach the restaurant.

Simple, isn’t it? You don’t need to calculate exhaustively all road lengths in advance (especially when you are hungry!). You just have to follow minimum path length road at a given junction. This reduces a lots of wasteful computations.

Greedy Algorithms When To Use

Lets look at the path finding question we were looking at in the previous slide.

Greed is not always good- you may end up with a non-optimal solution (using more fuel than you could have). This is the natural trade-off for being a short-term visionary rather than a long-term visionary. Let me give you an elementary example where it fails. See the following directed network:

Going by the intuition, you would choose first A and then you are stuck with the road of length 99. So you end up moving 100 units rather than a possible 10- had you visited B first, which did not seem attractive then. So greedy algorithm fails in this case. So why even use it? Because many times it works giving optimal solution while simply applying layman instincts. It turns out this network does have a greedy optimal solution but there computations must be done before leaving- in an intelligent manner. It is called Djikstra’s algorithm. This network is too simplistic to feel the algorithm*, and is best used for counterexamples. It’ll need a complex network to appreciate this algorithm and I leave it for another day.

As with all things algorithmic, we can’t leave applications to hope and therefore NEED PROOFS of whether our suggested greedy algorithms work or not. When the greedy method doesn’t work, we look forward to something called dynamic programming methods.

Now, lets look at some examples where greedy algorithm works.

Activity Selection Problem

You are given n activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

Example:

Consider the following 6 activities. 
         start[]  =  {1, 3, 0, 5, 8, 5};
         finish[] =  {2, 4, 6, 7, 9, 9};
    The maximum set of activities that can be executed 
    by a single person is {0, 1, 3, 4}

The greedy choice is to always pick the next activity whose finish time is least among the remaining activities and the start time is more than or equal to the finish time of previously selected activity. We can sort the activities according to their finishing time so that we always consider the next activity as minimum finishing time activity.

Sort the activities according to their finishing time
Select the first activity from the sorted array and print it.
Do following for remaining activities in the sorted array.
…….a) If the start time of this activity is greater than the finish time of previously selected activity then select this activity and print it.

An example code to clarify it further :

// Prints a maximum set of activities that can be done by a single
        // person, one at a time.
        //  n   -->  Total number of activities
        //  s[] -->  An array that contains start time of all activities
        //  f[] -->  An array that contains finish time of all activities ( sorted ) 
        void printMaxActivities(int s[], int f[], int n)
        {
            int i, j;
         
            printf ("Following activities are selected \n");
         
            // The first activity always gets selected
            i = 0;
            printf("%d ", i);
         
            // Consider rest of the activities
            for (j = 1; j < n; j++)
            {
              // If this activity has start time greater than or equal to the finish
              // time of previously selected activity, then select it
              if (s[j] >= f[i])
              {
              printf ("%d ", j);
              i = j;
              }
            }
        }

How does Greedy Choice work for Activities sorted according to finish time?

Let the give set of activities be S = {1, 2, 3, ..n} and activities be sorted by finish time. The greedy choice is to always pick activity 1. How come the activity 1 always provides one of the optimal solutions. We can prove it by showing that if there is another solution B with first activity other than 1, then there is also a solution A of same size with activity 1 as first activity. Let the first activity selected by B be k, then there always exist A = {B – {k}} U {1}.

(Note that the activities in B are independent and k has smallest finishing time among all. Since k is not 1, finish(k) >= finish(1)).

Question 1: Bulbs

N light bulbs are connected by a wire.

Each bulb has a switch associated with it, however due to faulty wiring, a switch also changes the state of all the bulbs to the right of current bulb.

Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs.

You can press the same switch multiple times.

Note : 0 represents the bulb is off and 1 represents the bulb is on.

Example:

Input 1:
    A = [1]Output 1:
    0Explanation 1:
    There is no need to turn any switches as all the bulbs are already on.Input 2: 
    A = [0 1 0 1]Output 2:
    4Explanation 2:
	press switch 0 : [1 0 1 0]
	press switch 1 : [1 1 0 1]
	press switch 2 : [1 1 1 0]
	press switch 3 : [1 1 1 1]

Solution:

You will never need to press the same switch twice. Why? Because it is equivalent to not pressing the switch and you will end up with the same state as before. So we can always solve the problem in at most n switch flips.

The order in which you press the switch does not affect the final state.

Example:

Input : [0 1 0 1]Case 1:
	Press switch 0 : [1 0 1 0]
	Press switch 1 : [1 1 0 1]
	
Case 2:
	Press switch 1 : [0 0 1 0]
	Press switch 0 : [1 1 0 1]

Therefore we can choose a particular order. To make things easier lets go from left to right. At the current position if the bulb is on we move to the right, else we switch it on. This works because changing any switch to the right of it will not affect it anymore.

int bulbs(vector<int> &A) {
		    int state= 0, ans = 0;
		    for (int i = 0;i < A.size();i++) {
			    if (A[i] == state) {
				    ans++;
				    state = 1 - state;
			    }
		    }
		    return ans;
	    }

Question 2: Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than floor(n/2) times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example :

Input : [2, 1, 2]
Return  : 2 which occurs 2 times which is greater than 3/2.

Solution:

Lets say you find 2 elements x and y which are different in the array. If you removed those 2 elements, would the majority element change ?

If we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. Loop through each element and maintains a count of the element that has the potential of being the majority element. If next element is same then increments the count, otherwise decrements the count. If the count reaches 0 then update the potential index to the current element and reset count to 1.

int majorityElement(vector<int> &num) {
            int majorityIndex = 0;
            for (int count = 1, i = 1; i < num.size(); i++) {
                num[majorityIndex] == num[i] ? count++ : count--;
                if (count == 0) {
                    majorityIndex = i;
                    count = 1;
                }
            }

            return num[majorityIndex];
        }

Question 3: Meeting rooms

Given an 2D integer array A of size N x 2 denoting time intervals of different meetings.

Where:

A[i][0] = start time of the ith meeting.
A[i][1] = end time of the ith meeting.

Find the minimum number of conference rooms required so that all meetings can be done.

Example Input

Input 1:

A = [      [0, 30]
            [5, 10]
            [15, 20]
     ]

Input 2:

A =  [     [1, 18]
            [18, 23]
            [15, 29]
            [4, 15]
            [2, 11]
            [5, 13]
      ]

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1:

Meeting one can be done in conference room 1 form 0 - 30.
Meeting two can be done in conference room 2 form 5 - 10.
Meeting one can be done in conference room 2 form 15 - 20 as it is free in this interval.

Explanation 2:

Meeting one can be done in conference room 1 from 1 - 18.
Meeting five can be done in conference room 2 from 2 - 11.
Meeting four can be done in conference room 3 from 4 - 15.
Meeting six can be done in conference room 4 from 5 - 13.
Meeting three can be done in conference room 2 from 15 - 29 as it is free in this interval.
Meeting two can be done in conference room 4 from 18 - 23 as it is free in this interval.

Solution:

The idea is to consider all events in sorted order.
Once the events are in sorted order, trace the number of meetings at any time keeping track of meetings that have started, but not ended.

Solution 1: Use min heap to store the meeting rooms end time. If new meeting start time is greater or equal than least element, update it.
If not, open a new meeting room. Report the min heap size at the end.
Time Complexity : O(NlogN).

Solution 2: Two sorted array of start time and end time. Two pointers to iterator start array and end array. Iterate the time line, the current time active meeting is num of start minus num of end.
Since need sort, still O(nlogn) solution, but fast than solution 1.