# 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:

- Assume that the jobs are sorted in ascending order of their starting time
- Let
`Max[i]`

define the*largest subset of compatible jobs starting at location i.*

How can we compute `Max[i]`

? Recursively!

- For every
`j > i`

, we first check whether jobs`i`

and`j`

are compatible. - If so, we calculate
`Max[j]+1`

as a candidate for`Max[i]`

. - We finally take then
*maximum*of all such candidates and assign it to`Max[i]`

- The base case is simply
`Max[N]`

(the last element), which is`1`

. - Since we recompute
`Max[i]`

multiple times, we canit by saving in a table/array, and reuse the pre-computed value.*memoize*

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.*