Activity Selection Problem using Greedy method in C++

In this tutorial, we will learn about the activity selection problem using the greedy approach in c++.

We will also see the example to understand the concept in a better way.

Activity Selection Problem using Greedy method

A greedy method is an algorithmic approach in which we look at local optimum to find out the global optimal solution.

Now, let’s look on the Activity selection problem,

We have given n activities with their start and finish times. So we need to 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.

Let,s look on example,

Consider the following 3 activities sorted by
by finish time.
     start[] = {9, 11, 20};
     finish[] = {20, 25, 30};
A person can perform at most two activities first and third.

Now, let’s see the greedy approach for this problem,

  1. First, we need to sort the activities in ascending order according to their finishing time.
  2. Then, select the first activity from the sorted array and print it.
  3. Then, do following for remaining activities in the sorted array.
    Check, if the starting time of this activity is greater than or equal to the finishing time of previously selected activity then select this activity and print it.

Now, let’s see the code for this problem.

Code implementation in C++

#include<bits/stdc++.h>
using namespace std;
//store the elements in ascending order on the basis of finishing time
bool comp(pair<int,int>i,pair<int,int>j){
    return i.second<j.second;
}
int main() {
      int n;
      cout<<"enter the number of elements:"<<endl;
      cin>>n;
      map<pair<int,int>,int>m;
      vector<pair<int,int> >vec(n);
      cout<<" Enter the starting time of activity:"<<endl;
      //store starting time
      for(int i=0;i<n;i++){
          cin>>vec[i].first;
      }
      cout<<"Enter the finishing time of activity:"<<endl;
      //store finishing time
      for(int i=0;i<n;i++){
          cin>>vec[i].second;
      }
      for(int i=0;i<n;i++){
          m[vec[i]]=i;
      }
      //sorting
      sort(vec.begin(),vec.end(),comp);
      //store the activity
      vector<int>v;
      vector<int>::iterator i;
      v.push_back(m[vec[0]]);
      pair<int,int>current=vec[0];
      for(int j=1;j<n;j++){
          if(vec[j].first>current.second){
              v.push_back(m[vec[j]]);
              current=vec[j];
          }
      }
      cout<<"Order in ehich the activity take place"<<endl;
      for(i=v.begin();i!=v.end();i++){
          cout<<*i+1<<" ";
      }
      cout<<endl;
  return 0;
}

OUTPUT

enter the number of elements:
6
Enter the starting time of activity:
1 3 0 5 8 5
Enter the finishing time of activity:
2 4 6 7 9 9
Order in ehich the activity take place
1 2 4 5

You may also learn,

Solution of N-Queen problem in C++ using Backtracking

Breadth first search (BFS) and Depth first search (DFS) for a Graph in C++

Minimum Spanning Tree for Graph in C++

Leave a Reply

Your email address will not be published. Required fields are marked *