Maximum Profit in Job Scheduling

January 8, 2024

medium

Problem #

You are given n jobs where each job consists of a start time, end time, and a profit. You can choose to perform these jobs such that no two jobs overlap. Find the maximum profit you can achieve by scheduling these jobs.

Example: #

Input: jobs = [(1, 3, 50), (2, 5, 20), (4, 6, 70), (6, 7, 30)] Output: 120 Explanation: The optimal job schedule is to do the job from 1 to 3 and then the job from 4 to 6. This gives a profit of 50 + 70 = 120.

Solution Approach: #

The solution can be approached using dynamic programming. First, sort the jobs based on their end time. Then, for each job, find the maximum profit including the current job. This requires finding the previous job that doesn’t overlap with the current job and adding its profit to the current job’s profit.

Algorithm Steps: #

Sort the jobs based on their end time.
Initialize a list dp of length n to store the maximum profit at each job.
Iterate through the sorted jobs, for each job:
- Perform a binary search to find the last non-overlapping job’s index.
- Update the dp list to store the maximum profit at this job by comparing the profit including this job and the profit excluding this job.
Return the maximum value in the dp list.

Code in Python: #

def jobScheduling(jobs):
    jobs.sort(key=lambda x: x[1])
    n = len(jobs)
    dp = [0] * n

    def binarySearch(i):
        lo, hi = 0, i - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if jobs[mid][1] <= jobs[i][0]:
                if jobs[mid + 1][1] <= jobs[i][0]:
                    lo = mid + 1
                else:
                    return mid
            else:
                hi = mid - 1
        return -1

    dp[0] = jobs[0][2]
    for i in range(1, n):
        profit = jobs[i][2]
        l = binarySearch(i)
        if l != -1:
            profit += dp[l]
        dp[i] = max(dp[i-1], profit)

    return dp[n-1]

# Example Usage
print(jobScheduling([(1, 3, 50), (2, 5, 20), (4, 6, 70), (6, 7, 30)]))  # Output: 120

Code Analysis #

The Python code provided solves the “Maximum Profit in Job Scheduling” problem using dynamic programming combined with binary search. The goal is to find the maximum profit that can be obtained by scheduling non-overlapping jobs, each defined by a start time, end time, and profit. Here’s an explanation of how the code works:

Sort Jobs by End Time:
```
jobs.sort(key=lambda x: x[1])
```
The jobs are sorted based on their end time. This is important because a job can only be considered after all jobs that end before it start.
Initialize Dynamic Programming Table:
```
dp = [0] * n
```
A dynamic programming table dp is initialized, where dp[i] will store the maximum profit that can be achieved by considering jobs up to the i-th job.
Binary Search Function:
```
def binarySearch(i):
    ...
```
This function is used to find the last job that does not overlap with the i-th job. It performs a binary search on the sorted jobs to find the closest job that ends before the i-th job starts.
Dynamic Programming Loop:
```
dp[0] = jobs[0][2]
for i in range(1, n):
    ...
```
The loop iterates over each job. For each job i:
- The profit profit is initially set to the profit of the i-th job.
- The binarySearch function is used to find the last non-overlapping job l.
- If such a job is found (l != -1), its profit is added to the current job’s profit.
- The dp[i] is set to the maximum of dp[i-1] (the maximum profit without including the current job) and the current job’s profit (including the best previous job).
Return the Maximum Profit:
```
return dp[n-1]
```
Finally, the function returns the last element of the dp array, which represents the maximum profit that can be achieved by scheduling the jobs.

Complexity Analysis: #

Time Complexity: O(n log n), where n is the number of jobs. The sorting of jobs takes O(n log n) time, and the binary search inside the loop also takes O(log n) time for each of the n jobs.
Space Complexity: O(n), as the space used is for the dynamic programming table dp with n elements.

This code efficiently solves the job scheduling problem by effectively combining sorting, binary search, and dynamic programming, highlighting a common pattern in optimization problems.

This problem demonstrates an efficient use of dynamic programming combined with binary search to optimize job scheduling for maximum profit, which is a classic problem in scheduling and optimization.