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.
1import java.util.*;
2
3public class JobScheduler {
4 public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
5 int n = startTime.length;
6 int[][] jobs = new int[n][3];
7 for (int i = 0; i < n; i++) {
8 jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
9 }
10 Arrays.sort(jobs, Comparator.comparingInt(a -> a[1]));
11 TreeMap<Integer, Integer> dp = new TreeMap<>();
12 dp.put(0, 0);
13
14 for (int[] job : jobs) {
15 int curProfit = dp.floorEntry(job[0]).getValue() + job[2];
16 if (curProfit > dp.lastEntry().getValue()) {
17 dp.put(job[1], curProfit);
18 }
19 }
20 return dp.lastEntry().getValue();
21 }
22}In this Java solution, a TreeMap is used to efficiently manage the dynamic programming states based on job end times. The TreeMap stores pairs of (endTime, maxProfit), allowing quick access to the best profit that can be achieved up to any point.
For each sorted job, we compute the maximum profit by checking the best non-overlapping job using floorEntry, and update the TreeMap if the current job's inclusion yields a better profit.
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.