6

Busy Man Problem Using C++

 2 years ago
source link: https://www.journaldev.com/62102/busy-man-problem-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Busy Man Problem Using C

Today, we’ll learn to solve the busy man problem using C++. It is another very popular problem from SPOJ(Sphere Online Judge). This problem is also known as the activity selection problem. This has already been asked about during many coding competitions. We’ll learn to solve this problem most efficiently. So without wasting any time, let’s get started.

Problem Statement for Solving the Busy Man Problem Using C++

You are a very busy person. You have a hectic schedule of activities. Your objective is to complete as many activities as possible. The input will be a schedule consisting of the start times and end times of all the activities.

For example,

Activities - Start_Time - End_Time
A1: 1 PM to 5 PM (Dating With Crush)
A2: 1 PM to 8 PM (Participate In Coding Contest)
A3: 2 PM to 5 PM (Watch Movie)
A4: 6 PM to 8 PM (Play DOTA)
A5: 9 PM to 12 PM (Study For Exam)
A6: 10 PM to 12 PM (Sleep Peacefully)
Ans: 3 activities
Explaination:
1 PM to 5 PM --> Dating With Crush
6 PM to 8 PM --> Play DOTA
10 PM to 12 PM --> Sleep Peacefully
Total_Count = 3

Approach

Key To Solving This Problem

Note that, this is a maximization problem. We have to maximize the total number of activities the person can complete throughout the day.

  • Let’s try some greedy choices.
    • Select the activity that starts first.
      • This is not a valid greedy choice because it doesn’t give any information about the activity that we’ll do next.
      • Suppose that, the activity which starts the earliest finishes at the end. The person would have no time to complete other activities.
    • Select the activity that ends earlier first.
      • Selecting an activity that is guaranteed to finish the earliest ensures that we’ve more time for the remaining activities.
      • That’ll maximise the total count of the activities that we complete throughout the day.

Thus, we’ll make the second criteria as our working rule.

Pseudocode

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

  • Greedy Choice: Select the activity that finishes early first.
  • Sort the activities in increasing order of finish times.
    • sort(ropes.begin(), ropes.end(), comparator);
    • Here, comparator is a custom comparison function.
  • Initialize a variable to store the answer.
    • int max_activities = 0;
  • Start iterating over the sorted vectors.
    • for(int i = 0; i < N; i++)
    • During each iteration, fulfil the greedy choice. i.e. select the activity that finishes early first. Increase the count.
      • max_activities++;
  • Finally, return the answer.
    • return max_activities;

Greedy Problem Busy Man Using C++ Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int> p1, pair<int, int> p2)
{
return p1.second < p2.second;
}
int main()
{
// take the input
cout << "Enter the total number of activities" << endl;
int N;
cin >> N;
// vector to store the start time and the end time of each activity
vector <pair <int, int>> activities(N);
cout << "Enter the start times and end times of all the activities" << endl;
for(int i = 0; i < N; i++)
{
int start_time, end_time;
cin >> start_time >> end_time;
activities[i] = make_pair(start_time, end_time);
}
// logic to implement the activity selection solution
// sort the activities according to the finishing time
sort(activities.begin(), activities.end(), compare);
// start picking the activities
// always pick the first activity
int count = 1;
int fin = activities[0].second;
// and iterate over the remaining activities
for(int i = 1; i < N; i++)
{
// if the next activity starts after the finishing time
// of the second activity we can complete the next activity
if(activities[i].first >= fin)
{
// update the new finishing time
fin = activities[i].second;
// update the count of completed activities
count++;
}
}
cout << "The maximum number of doable activites are: " << count << endl;
return 0;
}
Busy Man Problem Code
Busy Man Problem Code

Output

Busy Man Problem Output
Busy Man Problem Output

Conclusion

In this article, we learned to solve the busy man problem using C++. We used the STL(Standard Template Library) sort function to make use of our greedy choice. In the end, we 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/61089/euclids-division-lemma-cpp

https://www.journaldev.com/56852/binary-trees-bfs-traversal-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK