Question

link

Given a set of n jobs with [start time, end time, cost], find a subset so that no 2 jobs overlap and the cost is maximum.

Let’s assume the input is already sorted by start_time.

Solution

Somebody mentioned Interval Graph, so check it out if you interested!

I am going to discuss both DP and recursive solution.

This question reminds me of [Question] 0-1 Knapsack Problem and [Question] Coin Change Problem, cuz the basic idea is to compare 2 conditions:

1. include current element
2. or, not include current element

A very good DP solution is presented in here. The code below is written by me and it’s very intuitive to read.

Leave me a comment if you have questions. And one more thing~ Happy new year!

Code

Dp

private int dpSolution(Job[] jobs, int size) {
    int[] dp = new int[size];
    dp[size - 1] = jobs[size - 1].cost;
    // cost of last job equals to just itself
    for (int k = size - 2; k >= 0; k--) {
        int next = findNextJob(jobs, k);
        int includeK = jobs[k].cost;
        if (next < size) {
            includeK += dp[next];
        }
        int excludeK = dp[k + 1];
        dp[k] = Math.max(includeK, excludeK);
    }
    return dp[0];
}

private int findNextJob(Job[] jobs, int k) {
    int finishTime = jobs[k].finish;
    int next = k + 1;
    while (next < jobs.length) {
        if (jobs[next].start < finishTime) {
            next++;
        } else {
            break;
        }
    }
    return next;
}

Recursion

public int recursiveSolution(Job[] jobs, int size, int k) {
    // max cost from (k)th job and onwards
    if (k == size) {
        return 0;
    }
    // (k)th job must not conflict with any previous job
    int next = findNextJob(jobs, k);
    int includeK = jobs[k].cost + recursiveSolution(jobs, size, next);
    int excludeK = recursiveSolution(jobs, size, k + 1);
    return Math.max(includeK, excludeK);
}

private int findNextJob(Job[] jobs, int k) {
    int finishTime = jobs[k].finish;
    int next = k + 1;
    while (next < jobs.length) {
        if (jobs[next].start < finishTime) {
            next++;
        } else {
            break;
        }
    }
    return next;
}