Wed. Oct 5th, 2022

Hello Android

All android in one place

Busy Man Problem Using C++

3 min read

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

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


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.


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.
  • 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.
  • Finally, return the answer.

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

	cout << "The maximum number of doable activites are: " << count << endl;

	return 0;
Busy Man Problem Code


Busy Man Problem Output
Busy Man Problem Output


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.

Leave a Reply

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

Hello android © All rights reserved. | Newsphere by AF themes.