This approach leverages sorting, dynamic programming, and binary search to solve the problem efficiently.
endTime.dp where dp[i] stores the maximum profit we can achieve by considering the first i jobs.Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for the dp array.
1from bisect import bisect_right
2
3def jobScheduling(startTime, endTime, profit):
4 jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
5 end_times = [job[1] for job in jobs]
6 dp = [0] * (len(jobs) + 1)
7
8 for i in range(1, len(jobs) + 1):
9 k = bisect_right(end_times, jobs[i-1][0])
10 dp[i] = max(dp[i-1], jobs[i-1][2] + dp[k])
11
12 return dp[-1]The solution begins by sorting the jobs in increasing order of their end times. This allows us to consider each job and decide whether to include it based on the results of previously solved subproblems stored in the dp array.
For each job, we perform a binary search using bisect_right to find the index of the last job that doesn't conflict with the current one, and update the maximum profit accordingly.
This approach uses dynamic programming to solve the problem by scanning jobs and keeping track of maximum profits without the need of an auxiliary data structure for overlap checking. Instead of binary search, it uses a precomputed array to track the last non-overlapping job for each job.
endTime.Time Complexity: O(n^2) due to the nested loop search for non-overlapping jobs.
Space Complexity: O(n) for the dp array.
1def jobScheduling(startTime, endTime, profit):
2 jobs = list(zip(startTime, endTime, profit))
3 jobs.sort(key=lambda x: x[1])
4 n = len(jobs)
5 dp = [0] * n
6 dp[0] = jobs[0][2]
7
8 for i in range(1, n):
9 # Include the current job
10 includeProfit = jobs[i][2]
11 l = 0
12 for j in range(i - 1, -1, -1):
13 if jobs[j][1] <= jobs[i][0]:
14 includeProfit += dp[j]
15 break
16
17 dp[i] = max(includeProfit, dp[i - 1])
18
19 return dp[-1]The Python solution sorts jobs by endTime and iterates through each job, computing the maximum profit by considering two cases: including or excluding the current job. It utilizes a nested loop to find the last non-overlapping job in an optimized way, considering constraints on input sizes.