Skip to content

Instantly share code, notes, and snippets.

@thmain
Created May 22, 2024 15:06
Show Gist options
  • Save thmain/f69752221cab2734ce81369624502935 to your computer and use it in GitHub Desktop.
Save thmain/f69752221cab2734ce81369624502935 to your computer and use it in GitHub Desktop.
import java.util.Arrays;
import java.util.Comparator;
public class MaximumProfitJobs {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int numJobs = profit.length; // Number of jobs
Job[] jobs = new Job[numJobs];
for (int i = 0; i < numJobs; ++i) {
jobs[i] = new Job(endTime[i], startTime[i], profit[i]);
}
Arrays.sort(jobs, Comparator.comparingInt(job -> job.endTime));
int[] dp = new int[numJobs + 1];
for (int i = 0; i < numJobs; ++i) {
int startTimeValue = jobs[i].startTime;
int profitValue = jobs[i].profit;
int latestNonConflictJobIndex = search(jobs, i, startTimeValue);
dp[i + 1] = Math.max(dp[i], dp[latestNonConflictJobIndex] + profitValue);
}
return dp[numJobs];
}
private int search(Job[] jobs, int endIndex, int targetTime) {
int low = 0;
int high = endIndex;
while (low < high) {
int mid = (low + high) / 2;
if (jobs[mid].endTime <= targetTime) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
private static class Job {
int endTime;
int startTime;
int profit;
public Job(int endTime, int startTime, int profit) {
this.endTime = endTime;
this.startTime = startTime;
this.profit = profit;
}
}
public static void main(String[] args) {
int [] start = {1, 2, 3, 3};
int [] end = {3, 4, 5, 6};
int [] profit = {50,10,40,70};
MaximumProfitJobs m= new MaximumProfitJobs();
System.out.println(m.jobScheduling(start, end, profit));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment