class Solution {
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 endTimeValue = jobs[i].endTime;
int startTimeValue = jobs[i].startTime;
int profitValue = jobs[i].profit;
int latestNonConflictJobIndex = upperBound(jobs, i, startTimeValue);
dp[i + 1] = Math.max(dp[i], dp[latestNonConflictJobIndex] + profitValue);
}
return dp[numJobs];
}
private int upperBound(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;
}
}
}
/*
Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job.
Profit obtained 150 = 20 + 70 + 60.*/| Associated Context | |
|---|---|
| Type | Code Snippet ( .java ) |
| Associated Tags | Array Subset Profit JobScheduling - The name of the class that provides a job scheduling algorithm endTime - A variable representing the end time for processing jobs profit - A constant representing the profit to calculate all results from an array (profit) numJobs - Each number of running jobs per second Arrays sort - A method used to sort two integers by comparing integer values. Sorting Job Scheduling Dynamic Programming Sorting Binary Search Time Complexity Comparator Upper Bound |
| 💡 Smart Description | The code snippet defines a class Solution with two methods. The jobScheduling method takes in an array of startTime and endTime, as input for the end time (startTime) and profit(profit). It creates new jobs based on certain conditions such as starting The code snippet implements a job scheduling algorithm that maximizes profit. It takes in arrays of start times, end times, and profits for each job, and returns the maximum profit that can be obtained by scheduling a subset of jobs without overlapping time intervals. |
| 🔎 Suggested Searches | Java code for job scheduling with end time and profit Algorithm to find maximum number of jobs in an array that add up to a specific value Java program to calculate upperBound between two arrays using Comparator comparator How to implement JobScheduling class in Java? Java code example for finding the highest index within another element Algorithm for job scheduling with start time, end time, and profit Java code for job scheduling with dynamic programming Sort jobs by end time in Java Binary search implementation for finding upper bound in Java Example input and output for job scheduling problem |
| Related Links | https://www.geeksforgeeks.org/arrays-in-java/ https://www.geeksforgeeks.org/arraylist-in-java/ https://www.geeksforgeeks.org/java/ https://www.geeksforgeeks.org/weighted-job-scheduling/ |
| Related People | Rohan Mallick |
| Sensitive Information | No Sensitive Information Detected |
| Shareable Link | https://ca772742-b4e2-4612-af82-29a364c1f0bb.pieces.cloud/?p=51cc4fa9f8 |