Maximum Profit In Job Scheduling - Leetcode Solution

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.

1