Largest Set of Compatible Jobs

Problem:

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)]

Return:

[(1, 4), (4, 7), (8, 11)]

Solution:

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:

1. Assume that the jobs are sorted in ascending order of their starting time
2. Let Max[i] define the largest subset of compatible jobs starting at location i.

How can we compute Max[i]? Recursively!

1. For every j > i, we first check whether jobs i and j are compatible.
2. If so, we calculate Max[j]+1 as a candidate for Max[i].
3. We finally take then maximum of all such candidates and assign it to Max[i]
4. The base case is simply Max[N] (the last element), which is 1.
5. 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 std::sort

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.

Complexity:

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, table and next. Hence this algorithm also has a space complexity of O(N).

Testing:

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.