Daily bit(e) of C++ | Maximum profit job schedule
Daily bit(e) of C++ #128, Common interview problem: Maximum profit for job schedule.
Given a list of N jobs, each with a start time, end time and profit, determine the maximum profit achievable by processing some jobs under the constraint that none overlap.
Assume start and end times within the range {0..50000} and half-open interval for start and end times, i.e. a job can start at the end time of a previous job.
For example, in the above list of jobs, the most profitable schedule consists of the two green jobs, with a total profit of 55.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/TqedjPoEo.
Solution
If we brute force this solution, we will end up with O(2^n) complexity, and it might seem that this would be the correct approach since job scheduling is an NP problem. However, since we have the start and end times of the jobs given to us, this is a much easier problem.
Consider the following: if we are considering job Q, the maximum possible profit will be either not running the job, i.e. the maximum profit achievable at start_time+1, or running the job, i.e. the profit of the job + maximum profit achievable at end_time.
This already points to a simple dynamic programming solution, processing the jobs in descending order of their start times.
However, we will go for a different solution.
If we scan the jobs in the order of their start times, we can chain a job Q to a previous sequence of jobs that have their end time at or before the start time of this job, and we want to pick the best (most profitable) such sequence.
We need two observations here:
no matter which sequences we chain, we end up with the same end time, only a different profit, so for each job, we generate only one chain
the sequences that were a valid chain for the current job will also be a valid chain for all future jobs (because their start time is at or after the current job), so we don’t have to remember them (only their profit, and only the best one)
Putting this together, we end up with an O(n*log(n)) solution:
