Weighted Program Scheduling Problem in C++
By Vikash AgarwalIn this tutorial, we will learn about the Weighted Program Scheduling Problem in C++ programming. We will limit our discussion to scheduling programs in a single-core processor.
Given a single-core processor and a set of programs that can be run on that processor. Each program is associated with a start time, end time, and profit gained from running that program.
Since the processor is single-core, multiple programs cannot be run simultaneously. Also, if a program ends at time t, then a new program can only be started at time > t.
The task is to prepare a valid schedule that maximizes the total profit.
Examples
Format: Job ID = (Start Time, End Time, Profit)
- Input: Job 1 = (1, 4, 10)
Job 2 = (4, 8, 20)
Output: Total profit = 20
Scheduled Job: –
Job 2
Explanation: There are only two jobs, but their running times overlap. So, we take the one with a higher profit, that is, Job 2. - Input: Job 1 = (1, 5, 60)
Job 2 = (4, 8, 100)
Job 3 = (6, 10, 60)
Output: Total profit = 120
Scheduled Jobs: –
Job 1, Job 3
Explanation: Taking Job 1, Job 3 gives a profit of 120. No other valid schedule gives a profit > 120. - Input: Job 1 = (1, 3, 20)
Job 2 = (3, 6, 20)
Job 3 = (5, 12, 100)
Job 4 = (7, 9, 70)
Job 5 = (10, 14, 60)
Output: Total profit = 150
Scheduled Jobs: –
Job 1, Job 4, Job 5
Explanation: Taking Job 1, Job 4, and Job 5 gives a profit of 150. No other valid schedule gives a profit > 150.
Idea
The most important observation in this problem is that it has an underlying optimal substructure property if the programs are evaluated in a specific order.
If we have a maximum profit schedule of all the programs that end before the current program ends and a maximum profit schedule of all the programs that end before the current program starts, then we can get the maximum profit schedule of the current set of programs by including or excluding the current program.
The above observation leads us to sort the programs by their ending times and then apply dynamic programming following the optimal substructure property.
Optimal Substructure Property
After sorting the programs by their ending times,
If we exclude the current program in the desired schedule, then the maximum profit schedule of the current set of programs will be equal to the maximum profit schedule of the set of programs that end before the current program ends.
If we include the current program in the desired schedule, then the maximum profit schedule of the current set of programs will be equal to the current program plus the maximum profit schedule of the set of programs that end before the current program starts.
Therefore, taking the maximum of the above two will give us the maximum profit schedule of the current set of programs.
We can backtrack the programs by storing relevant information about the transitions.
Algorithm
Initially, sort the programs by their ending times.
For the program at index (i),
Find the index (j) of the last program that ends before the current program starts. This can be done using a binary search since the programs are sorted by their ending times.
Calculate the total profit excluding the current program.
Exclusion profit = Max Schedule Profit (i – 1)
Calculate the total profit including the current program.
Inclusion profit = Max Schedule Profit (j) + Profit from current program.
Update the current schedule.
Backtrack the programs in the maximum profit schedule by maintaining the transitions in every step of dynamic programming.
C++ Implementation of the above Algorithm
Below is our given C++ program for Weighted Program Scheduling Problem:
#include <bits/stdc++.h>
using namespace std;
// A structure to store the programs.
struct program
{
int id;
// ID of the program.
int start_time;
// Starting time of the program.
int end_time;
// Ending time of the program.
int profit;
// Profit on running the program.
// Operator overloaded for sorting programs on the basis of ending time.
bool operator < (const program& prg) const
{
return end_time < prg.end_time;
}
};
// Comparator for sorting programs on the basis of program ID.
bool comparator (program prg1, program prg2)
{
return prg1.id < prg2.id;
}
/*
Returns the index of the max profit schedule of programs
to the left of 'cur_index' that can be run along with the
program indexed at 'cur_index' without any conflicts.
*/
int previous_runnable_schedule (vector <program> prg, int cur_index)
{
//Using modified binary search since programs are sorted by their ending times.
int left = 0, right = cur_index - 1;
while (left <= right)
{
int probe = (left + right) / 2;
/*
If the ending time of probe < the starting time of cur_index and
the ending time of probe + 1 < the starting time of cur_index,
then we need to search in the interval to the right of probe.
If the ending time of probe < the starting time of cur_index and
the ending time of probe + 1 >= the starting time of cur_index,
then probe is our required index.
If the ending time of probe >= the starting time of cur_index,
then we need to search in the interval to the left of probe.
*/
if (prg[probe].end_time < prg[cur_index].start_time)
{
if (probe == cur_index - 1 || prg[probe + 1].end_time >= prg[cur_index].start_time)
{
return probe;
}
left = probe + 1;
}
else
{
right = probe - 1;
}
}
return -1;
}
vector <program> max_profit_scheduling (vector <program> prg)
{
int n = prg.size ();
// Sort the programs according to their ending times.
sort (prg.begin(), prg.end());
// Maintain an array to store the max profit in scheduling of programs till current index.
int max_profit [n];
// max_profit[i] = maximum profit in scheduling of prg[0..i].
// Base Case -> If there is only one program, we will always take it.
max_profit[0] = prg[0].profit;
// Maintain an array to backtrack a schedule of programs that gives max profit.
int previous [n];
// There is no program prior to the first program.
previous[0] = -1;
// Maintain an array to track if a program is taken or not in a max profit schedule of programs till current index.
vector<bool> taken (n, false);
// taken[i] = true if ith program is taken in max profit schedule of prg[0..i], false otherwise.
// First program is taken.
taken[0] = true;
for (int i = 1; i < n; i++)
{
// Profit when the ith program is not included.
int profit_excluding_current_program = max_profit[i - 1];
// Profit when the ith program is included.
int profit_including_current_program = prg[i].profit;
/*
Getting the index prior to 'i' with the best schedule for programs
such that the current program can be run without any conflicts.
*/
int previous_index = previous_runnable_schedule (prg, i);
/*
Update the profit when the ith program is included if one or more programs
considered previously can be run without any conflicts with the current one.
*/
if (previous_index != -1)
{
profit_including_current_program += max_profit[previous_index];
}
// Update other variables accordingly.
if (profit_including_current_program > profit_excluding_current_program)
{
max_profit[i] = profit_including_current_program;
taken[i] = true;
previous[i] = previous_index;
}
else
{
max_profit[i] = profit_excluding_current_program;
previous[i] = i - 1;
}
}
vector <program> schedule;
// To store a max profit schedule.
int cur = n - 1;
while (cur != -1)
{
/*
If the current program is taken in max profit schedule of prg[0..cur],
then push it in the schedule.
*/
if (taken[cur])
{
schedule.push_back(prg[cur]);
}
// Update cur variable to backtrack the previous programs included in the max profit schedule.
cur = previous[cur];
}
return schedule;
}
// Displays the max profit schedule after sorting it by program ID.
void display (vector <program> schedule)
{
cout << "Maximum Profit Schedule: -\n\n";
int total_profit = 0;
sort (schedule.begin(), schedule.end(), comparator);
for (program p : schedule)
{
cout << "Job ID = " << p.id
<< ", Start Time = " << p.start_time
<< ", End Time = " << p.end_time
<< ", Profit = " << p.profit
<< "\n\n";
total_profit += p.profit;
}
cout << "Total Profit = " << total_profit;
}
// Driver Code.
int main ()
{
vector <program> prg;
// The following programs are taken for illustration: -
prg.push_back ({1, 1, 3, 20});
prg.push_back ({2, 3, 6, 20});
prg.push_back ({3, 5, 12, 100});
prg.push_back ({4, 7, 9, 70});
prg.push_back ({5, 10, 14, 60});
// Getting the max profit schedule.
vector <program> schedule = max_profit_scheduling (prg);
// Displaying the max profit schedule.
display (schedule);
return 0;
}
Output: –
Maximum Profit Schedule: -
Job ID = 1, Start Time = 1, End Time = 3, Profit = 20
Job ID = 4, Start Time = 7, End Time = 9, Profit = 70
Job ID = 5, Start Time = 10, End Time = 14, Profit = 60
Total Profit = 150
Complexity Analysis
Sorting takes O (N log N). Getting the previous runnable schedule for each program using modified binary search takes O (log N).
Therefore, the time complexity of the above code is O (N log N).
Auxiliary space of O (N) is used for storing maximum total profit as well as for backtracking the scheduled programs.
Therefore, the space complexity of the above code is O (N).
Leave a Reply