Solution For Maximum Profit In Job Scheduling

Problem:

You are given a list of jobs where every job has a start time, end time, and a profit assigned to it. Your task is to schedule the jobs in such a way that you get maximum profit while keeping the non-overlapping constraint (i.e. no two jobs should overlap in time). Return the maximum profit you can get.

Solution:

This problem can be solved using dynamic programming. The idea is to sort the jobs based on their ending time. We can solve the subproblems by considering two cases:

1. If we include the current job: In this case, we will consider the maximum profit we can get by scheduling the jobs that end before the start time of the current job and add the profit of the current job to it.

2. If we exclude the current job: In this case, we will consider the maximum profit we can get by scheduling the jobs that end before the end time of the previous job.

We will maintain an array dp[i] where dp[i] represents the maximum profit we can get by scheduling the first i jobs. We can calculate dp[i] by considering the above cases and taking the maximum of the two.

The time complexity of this solution is O(n^2) where n is the number of jobs. However, we can optimize it by using binary search to find the index of the job that ends before the start time of the current job. This will bring down the time complexity to O(nlogn).

Here is the Python code for the optimized solution:

“`
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
dp = [0]*len(jobs)
dp[0] = jobs[0][2] for i in range(1, len(jobs)):
start_time = jobs[i][0] prev_profit = dp[i-1] prev_idx = self.binary_search(jobs, i)
if prev_idx is not None:
prev_profit = dp[prev_idx] curr_profit = prev_profit+jobs[i][2] dp[i] = max(dp[i-1], curr_profit)
return dp[-1]

def binary_search(self, jobs, i):
    start, end = 0, i-1
    while start <= end:
        mid = (start+end)//2
        if jobs[mid][1] <= jobs[i][0]:
            if jobs[mid+1][1] <= jobs[i][0]:
                start = mid+1
            else:
                return mid
        else:
            end = mid-1
    return None

“`

In the above code, we first sort the jobs based on their end time. We then initialize dp[0] to be the profit of the first job. We then loop through the jobs starting from the second job and compute dp[i] using the two cases mentioned above. We use binary search to find the index of the job that ends before the start time of the current job. We then take the maximum of the two cases to compute dp[i]. Finally, we return dp[-1] which gives us the maximum profit we can get by scheduling all the jobs.

Step by Step Implementation For Maximum Profit In Job Scheduling

/**
 * You are given an array of integers jobs where jobs[i] = [starti, endi, profiti] 
 * represents a job that starts at starti and ends at endi with a profit of profiti.
 * 
 * You're given the starting and ending times of a set of jobs in the form of two arrays 
 * startTime and endTime. startTime[i] and endTime[i] represent the i-th job's start and 
 * end time.
 * 
 * Return the maximum profit you can make from these jobs.
 * 
 * Constraints:
 * 
 * 1 <= startTime.length == endTime.length <= 100
 * 1 <= startTime[i] < endTime[i] <= 1000
 * 1 <= profit[i] <= 1000
 */

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // sort the jobs by increasing order of ending time
        int[][] jobs = new int[startTime.length][3];
        for (int i = 0; i < startTime.length; i++) {
            jobs[i][0] = startTime[i];
            jobs[i][1] = endTime[i];
            jobs[i][2] = profit[i];
        }
        Arrays.sort(jobs, new Comparator() {
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        
        // dp[i] represents the maximum profit that can be made by completing 
        // at most i jobs
        int[] dp = new int[jobs.length];
        dp[0] = jobs[0][2];
        for (int i = 1; i < jobs.length; i++) {
            // compare the current job's profit with the profit that can be made
            // by completing the current job and the best job before it
            dp[i] = Math.max(jobs[i][2], dp[i-1]);
            
            // check if there is a job that can be completed before the current
            // job starts
            for (int j = i-1; j >= 0; j--) {
                if (jobs[j][1] <= jobs[i][0]) {
                    // if there is, update the maximum profit by adding the 
                    // profit of the current job to the profit of the job that 
                    // can be completed before it starts
                    dp[i] = Math.max(dp[i], jobs[i][2] + dp[j]);
                    break;
                }
            }
        }
        
        // return the maximum profit that can be made by completing all the jobs
        return dp[jobs.length-1];
    }
}

This is a classic dynamic programming problem. We can define the state dp[i] to be the maximum profit we can make by scheduling jobs up to and including the i-th job. Then, the recurrence relation is as follows:

dp[i] = max(dp[i-1], dp[j]) + profit[i]

where j is the largest index such that j < i and job[j] does not conflict with job[i]. We can solve this in O(n^2) time by considering all possible choices of j for each i.

Alternatively, we can solve this in O(n log n) time using a greedy approach. First, we sort the jobs by increasing order of start time. Then, we schedule the first job and iteratively schedule the next job that starts after the previous job ends. The profit for each job is added to the total profit.

/**
 * @param {number[]} startTime
 * @param {number[]} endTime
 * @param {number[]} profit
 * @return {number}
 */
var jobScheduling = function(startTime, endTime, profit) {
    // sort by end time
    let jobs = [];
    for (let i = 0; i < startTime.length; i++) {
        jobs.push([startTime[i], endTime[i], profit[i]]);
    }
    jobs.sort((a, b) => a[1] - b[1]);
    
    // dp[i] is the max profit up to jobs[i]
    let dp = new Array(jobs.length).fill(0);
    dp[0] = jobs[0][2];
    
    for (let i = 1; i < jobs.length; i++) {
        // profit if we don't do this job
        let profitNoJob = dp[i-1];
        
        // profit if we do this job
        let profitJob = jobs[i][2];
        let j = binarySearch(jobs, jobs[i][0]);
        if (j >= 0) {
            profitJob += dp[j];
        }
        
        // take the max of the two options
        dp[i] = Math.max(profitNoJob, profitJob);
    }
    
    return dp[jobs.length - 1];
};

// binary search for the first job that starts after job[i][0]
function binarySearch(jobs, target) {
    let left = 0;
    let right = jobs.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (jobs[mid][0] === target) {
            return mid;
        } else if (jobs[mid][0] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return right;
}

class Solution {
public:
    int jobScheduling(vector& startTime, vector& endTime, vector& profit) {
        int n = startTime.size();
        vector> jobs(n);
        for(int i = 0; i < n; i++) {
            jobs[i] = {endTime[i], profit[i]};
        }
        // sort the jobs by end time
        sort(jobs.begin(), jobs.end());
        // dp[i] represents the maximum profit we can make by scheduling jobs up to the i-th job
        vector dp(n);
        dp[0] = jobs[0].second;
        for(int i = 1; i < n; i++) {
            // we can either schedule the i-th job or not schedule it
            // if we don't schedule it, then our profit will be the same as the profit for scheduling jobs up to the i-1-th job
            // if we do schedule it, then our profit will be the profit for the i-th job plus the maximum profit we can make by scheduling jobs up to the j-th job 
            //      where j is the largest index such that the j-th job ends before the i-th job starts
            dp[i] = jobs[i].second;
            int j = i - 1;
            while(j >= 0 && jobs[j].first > jobs[i].first) {
                j--;
            }
            if(j != -1) {
                dp[i] += dp[j];
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

using System; 

public class Solution { 

// DP solution for Maximum Profit in Job Scheduling 

// We sort the jobs by their start time 

Array.Sort(jobs, (a, b) => a[0] - b[0]); 

// We create an array to store the maximum profit 

// up to the current job 

int[] dp = new int[jobs.Length]; 

dp[0] = jobs[0][2]; 

// We start from the second job 

for (int i = 1; i < jobs.Length; i++) { 

// We take the maximum profit from the 

// previous jobs 

int profit = jobs[i][2]; 

// We find the latest job that doesn't 

// conflict with the current job 

int l = LatestNonConflict(jobs, i); 

// If we found a latest job that doesn't 

// conflict, we add the profit of it to 

// the current profit 

if (l != -1) 

profit += dp[l]; 

// We update the maximum profit from 

// the previous jobs 

dp[i] = Math.Max(profit, dp[i - 1]); 

} 

// After the loop we return the last 

// element of the dp array as it will 

// contain the maximum profit 

return dp[dp.Length - 1]; 

} 

// A function to find the latest job (in 

// sorted array) that doesn't conflict 

// with the job[i] 

static int LatestNonConflict(int[][] arr, int i) 

{ 

for (int j = i - 1; j >= 0; j--) { 

if (arr[j][1] <= arr[i][0]) 

return j; 

} 

return -1; 

} 

}