Maximum Profit in Job Scheduling
January 8, 2024
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 lengthn
to store the maximum profit at each job.  Iterate through the sorted jobs, for each job:
 Perform a binary search to find the last nonoverlapping 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[i1], profit)
return dp[n1]
# 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 nonoverlapping 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, wheredp[i]
will store the maximum profit that can be achieved by considering jobs up to thei
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 thei
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 thei
th job.  The
binarySearch
function is used to find the last nonoverlapping jobl
.  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 ofdp[i1]
(the maximum profit without including the current job) and the current job’s profit (including the best previous job).
 The profit

Return the Maximum Profit:
return dp[n1]
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 then
jobs.  Space Complexity: O(n), as the space used is for the dynamic programming table
dp
withn
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.