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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Profit in Job Scheduling

Number: 1352

Difficulty: Hard

Paid? No

Companies: DoorDash, Amazon, Snowflake, Airbnb, Bloomberg, Pinterest, Microsoft, Goldman Sachs, Verkada, PhonePe, Oracle, PayPal, WeRide, Google, Urban Company, Flipkart, Swiggy, Databricks, Adobe, Apple, Akuna Capital, oyo, Zeta, Pony.ai

Problem Description

Given three arrays startTime, endTime, and profit representing a list of jobs, each job has a start time, an end time, and a profit. The goal is to find the maximum profit achievable by scheduling non-overlapping jobs. A job can start at the same time another job ends.

Key Insights

  • Sort jobs based on their end times to simplify finding non-conflicting jobs.
  • Use dynamic programming where the state represents the maximum profit until a given point.
  • For each job, perform a binary search to find the last job that ends before the current job’s start time.
  • The recurrence relation is: dp[i] = max(dp[i-1], profit[i] + dp[index]) where dp[index] is from the latest non-conflicting job.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and binary search for each job. Space Complexity: O(n) for the dp arrays.

Solution

The solution begins by sorting the jobs by their end times. For each job, a binary search is used to quickly locate the last job that does not conflict with the current job (i.e., whose end time is less than or equal to the current job’s start time). Then, using dynamic programming, the maximum profit is updated by choosing whether to include the current job or skip it. Two parallel arrays (or lists) are maintained: one for the end times of the jobs considered so far, and another to store the corresponding maximum profit at those times. This approach efficiently computes the answer while keeping time complexity within acceptable bounds.

Code Solutions

import bisect

def jobScheduling(startTime, endTime, profit):
    # Combine the jobs and sort them by end time.
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    
    # dp_end_times stores the end times and dp_profits stores the corresponding maximum profit.
    dp_end_times = [0]
    dp_profits = [0]
    
    # Process each job in order.
    for s, e, p in jobs:
        # Find the index of the last job that finishes before or at the start of the current job using binary search.
        index = bisect.bisect_right(dp_end_times, s)
        current_profit = dp_profits[index - 1] + p  # Profit if we take current job.
        
        # If taking current job increases the overall profit, update the dp arrays.
        if current_profit > dp_profits[-1]:
            dp_end_times.append(e)
            dp_profits.append(current_profit)
    
    return dp_profits[-1]

# Example usage:
print(jobScheduling([1,2,3,3], [3,4,5,6], [50,10,40,70]))
← Back to All Questions