Skip to content

Instantly share code, notes, and snippets.

@pjoshi30
Created March 3, 2016 04:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pjoshi30/43a8844525c85dca8538 to your computer and use it in GitHub Desktop.
Save pjoshi30/43a8844525c85dca8538 to your computer and use it in GitHub Desktop.
O(n(log(n))) solution to the weighted job scheduling problem
import java.io.*;
import java.util.*;
/**
* nlogn solution to http://www.geeksforgeeks.org/weighted-job-scheduling/
*/
class Solution {
public static void main(String[] args) {
List<Job> jobs = Arrays.asList(new Job(3, 10, 20),new Job(1, 2, 50), new Job(6, 19, 100),new Job(2, 100, 200));
System.out.println("Max profit = " + findMax(jobs));
}
private static int findMax(List<Job> jobs){
if(jobs == null || jobs.isEmpty()){
return 0;
}
int n = jobs.size();
Collections.sort(jobs, new Comparator<Job>() {
public int compare(Job j1, Job j2){
return (int)(j1.end - j2.end);
}
});
int[] profit = new int[n];
profit[0] = jobs.get(0).profit;
for(int i = 1; i < n; i++){
int includingJobProfit = jobs.get(i).profit;
int nonConflictingJobIndx = findNonConflictingJob(jobs, i);
if(nonConflictingJobIndx >= 0){
includingJobProfit += profit[nonConflictingJobIndx];
}
profit[i] = Math.max(includingJobProfit, profit[i-1]);
}
return profit[n-1];
}
private static int findNonConflictingJob(List<Job> jobs, int i){
//Find the job with end time less than the current job i's start time
int lo = 0;
int hi = i-1;
int lastSuccMid = -1;
//Modified version of binary search to find the closest previous element
//to the current element. Running time is O(log(n))
while(lo <= hi){
int mid = (lo + hi) >>> 1;
if(jobs.get(mid).end <= jobs.get(i).start){
lo = mid+1;
lastSuccMid = mid;
} else {
hi = mid-1;
}
}
return lastSuccMid;
}
}
class Job {
final long start;
final long end;
final int profit;
Job(long start, long end, int profit){
this.start = start;
this.end = end;
this.profit = profit;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment