Weighted Job Scheduling

Here is the problem description from GeeksforGeeks:

Given N jobs where every job is represented by following three elements of it.
1) Start Time
2) Finish Time.
3) Profit or Value Associated.
Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Example:

Input: Number of Jobs n = 4
       Job Details {Start Time, Finish Time, Profit}
       Job 1:  {1, 2, 50} 
       Job 2:  {3, 5, 20}
       Job 3:  {6, 19, 100}
       Job 4:  {2, 100, 200} 

Output: The maximum profit is 250.

This is so much similar to the 0-1 knapsack problem.  So we need to find the dynamic function, first of all, we sort the job by end time, then for each job k, DP(k) indicate the maximum profit which includes job[k], the final maximum profit should be the maximum value of DP(k)|0<=k<n.

 public class Job implements Comparable<Job>{

int start, end, profit;

public int compareTo(Job other){

return this.end - other.end;

}

}

public int maxProfit(Job[] jobs){

//table[i] store the max profit including ith job

int[] table = new int[jobs.length];

Arrays.sort(jobs);

table[0] = jobs[0].profit;

for(int k = 1; k<jobs.length; k++){

int max = Integer.MIN_VALUE;

int m = binarySearch(jobs, 0, k-1, jobs[k].start);

while(m>=0)

max = Math.max(max, table[m--]);

table[k] = max + jobs[k].profit;

}

int max = Integer.MIN_VALUE;

for(int k=0; k<jobs.length; k++){

max = Math.max(table[k], max);

}

return max;

}

public int binarySearch(Job[] jobs, int start, int end, int k){

if(jobs[start].end > k)

return start-1;

while(start<end-1){

int mid = (start+end)>>>1;

if(jobs[mid].end > k)

end = mid;

else

start = mid;

}

return jobs[end].end<=k?end:start;

}