We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Profit in Job Scheduling

Difficulty: Hard

Problem Description

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 are 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.

Key Insights

  • Each job has a specified time interval and associated profit.
  • The problem can be solved using dynamic programming combined with binary search.
  • The jobs should be sorted based on their end times to facilitate efficient selection of non-overlapping jobs.
  • A binary search can be used to find the last job that does not overlap with the currently selected job.

Space and Time Complexity

Time Complexity: O(n log n) - sorting the jobs takes O(n log n) and finding the last non-overlapping job takes O(log n) for each job, resulting in O(n log n). Space Complexity: O(n) - to store the dynamic programming array for maximum profits.

Solution

To solve the problem, we will:

  1. Pair up the jobs with their respective start times, end times, and profits.
  2. Sort these pairs based on the end times of the jobs.
  3. Utilize a dynamic programming array where each entry at index i represents the maximum profit obtainable up to job i.
  4. For each job, use binary search to find the last job that ends before the current job starts.
  5. Update the maximum profit for the current job either by taking it (adding its profit to the profit of the last non-overlapping job) or skipping it (taking the profit of the previous job).

Code Solutions

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    dp = [0] * len(jobs)
    
    for i in range(len(jobs)):
        start, end, prof = jobs[i]
        dp[i] = prof
        
        # Find the last job that doesn't overlap
        j = binarySearch(jobs, i)
        if j != -1:
            dp[i] += dp[j]
        
        # Update the maximum profit
        if i > 0:
            dp[i] = max(dp[i], dp[i-1])
    
    return dp[-1]

def binarySearch(jobs, index):
    low, high = 0, index - 1
    while low <= high:
        mid = (low + high) // 2
        if jobs[mid][1] <= jobs[index][0]:
            if jobs[mid + 1][1] <= jobs[index][0]:
                low = mid + 1
            else:
                return mid
        else:
            high = mid - 1
    return -1
← Back to All Questions