[Facebook] Scheduling Jobs with Max Cost

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;
}