Created
March 3, 2016 04:46
-
-
Save pjoshi30/43a8844525c85dca8538 to your computer and use it in GitHub Desktop.
O(n(log(n))) solution to the weighted job scheduling problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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