You are given a list of jobs to be done, where each job is represented by a start time and end time. Two jobs are compatible if they don’t overlap. Find the largest subset of compatible jobs.
For example, given the following jobs (there is no guarantee that jobs will be sorted):
[(0, 6), (1, 4), (3, 5), (3, 8), (4, 7), (5, 9), (6, 10), (8, 11)]
[(1, 4), (4, 7), (8, 11)]
There are total subsets of the array of size
N. Testing and comparing all of them for compatibility is prohibitively expensive.Instead, we should use Dynamic Programming to derive an efficient polynomial-time algorithm. An important step in devising the algorithm is to find a recursive structure in the problem:
- Assume that the jobs are sorted in ascending order of their starting time
Max[i]define the largest subset of compatible jobs starting at location i.
How can we compute
- For every
j > i, we first check whether jobs
- If so, we calculate
Max[j]+1as a candidate for
- We finally take then maximum of all such candidates and assign it to
- The base case is simply
Max[N](the last element), which is
- Since we recompute
Max[i]multiple times, we can memoize it by saving in a table/array, and reuse the pre-computed value.
Here is the code. We typedef a
Job as a
std::pair. One advantage of a pair is that sorting the jobs in ascending order becomes a single line code with
using Job = std::pair<int, int>;
We can define a helper function to check whether two Jobs intersect.
The next method uses dynamic programming and additional arrays for constructing the largest compatible set of jobs.
The double loop in the body of
largest_compatible makes the complexity obvious. We iterate over the array once, and for each element perform
O(N) work (by iterative over all subsequent elements). Hence, the complexity of the algorithm is . We are keeping additional 1-dimensional arrays,
next. Hence this algorithm also has a space complexity of
Start with comparing empty or a single element array. We can use C++ initializer list to initialize the vector of pairs.
Finally, here is the unit test for the original example in the problem.
Originally published at https://cppcodingzen.com on August 31, 2020.