Busy Man Problem Using C++

Filed Under: C++
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

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