We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range. If you choose a job that ends at time X you will be able to start another job that starts at time X.

For example:

startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] Output: 120. The subset chosen is the first and fourth job. Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] Output: 150. The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60.

startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] Output: 6

Dynamic Programming Solution

This problem can be solved using dynamic programming. We can sort the jobs by their end times. Then, for each job, we have two choices: either include it in the solution or exclude it. If we include the job, we need to find the latest non-overlapping job that finishes before the current job starts. We can use binary search to find this job. The maximum profit can be calculated using the following recurrence relation:

dp[i] = max(dp[i-1], profit[i] + dp[j])

where dp[i] is the maximum profit we can obtain by considering the first i jobs, and j is the latest non-overlapping job that finishes before the ith job starts.

Code

import bisect

def job_scheduling(start_time, end_time, profit):
    jobs = sorted(zip(start_time, end_time, profit), key=lambda x: x[1])
    start_times = [s for s, e, p in jobs]
    dp = [0] * len(jobs)
    dp[0] = jobs[0][2]

    for i in range(1, len(jobs)):
        current_profit = jobs[i][2]
        prev_job_index = bisect.bisect_right(start_times, jobs[i][0], hi=i-1)
        if prev_job_index > 0:
            current_profit += dp[prev_job_index-1]
        dp[i] = max(dp[i-1], current_profit)

    return dp[-1]

# Example usage
start_time = [1, 2, 3, 3]
end_time = [3, 4, 5, 6]
profit = [50, 10, 40, 70]
print(job_scheduling(start_time, end_time, profit))  # Output: 120

start_time = [1, 2, 3, 4, 6]
end_time = [3, 5, 10, 6, 9]
profit = [20, 20, 100, 70, 60]
print(job_scheduling(start_time, end_time, profit))  # Output: 150

start_time = [1, 1, 1]
end_time = [2, 3, 4]
profit = [5, 6, 4]
print(job_scheduling(start_time, end_time, profit))  # Output: 6

Brute Force Solution

A brute force solution would involve considering all possible subsets of jobs and finding the maximum profit among the subsets that do not have overlapping jobs. This would have an exponential time complexity of O(2^n), where n is the number of jobs.

Big(O) Run-Time Analysis

The time complexity of the dynamic programming solution is O(n log n), where n is the number of jobs. Sorting the jobs takes O(n log n) time. The binary search in the loop also takes O(log n) time, and the loop runs n times. So, the overall time complexity is O(n log n).

Big(O) Space Usage Analysis

The space complexity of the dynamic programming solution is O(n), where n is the number of jobs. This is because we need to store the dp array of size n.

Edge Cases

• Empty input: If the input arrays are empty, the function should return 0.
• Overlapping jobs with zero profit: If there are overlapping jobs with zero profit, the function should still return the maximum profit, which might be 0 if no jobs are selected.
• Large input: The code should be able to handle large input sizes (up to 5 * 10^4 as specified in the constraints) without exceeding the time limit.
• Negative Profits: If there are negative profits, the algorithm should still select the jobs that maximize the profit (sum of profits), but can return 0 if all profits are negative.