1235. Maximum Profit in Job Scheduling

Problem Description

In this scheduling problem, we are given n different jobs, each job has a start time, end time, and the profit it yields upon completion. Our primary goal is to find the maximum total profit earned by completing jobs that do not overlap in time. We are allowed to choose jobs in such a way that if one job ends at a certain time X, the next job can start exactly at X.

The difficulty lies in selecting the optimal set of jobs that maximize our profit while ensuring their time periods do not clash. This is akin to having a busy schedule and trying to fit in as many high-paying gigs as possible, without them overlapping, to maximize earnings.

Intuition

The trick to solving this problem lies in dynamic programming, which allows us to break down the problem into smaller sub-problems and build a solution incrementally.

Firstly, we need to sort the jobs by their end times to process them in order. This ordering will help address jobs sequentially and pick the best possible previous job that doesn't overlap.

With each job considered, we must decide whether to take this job along with the optimal set of jobs before it, or to skip it and stick with the previous optimal set. Here's where dynamic programming comes into play:

We use a Dynamic Programming (DP) table dp where each dp[i] represents the maximum profit that can be achieved by scheduling jobs up to the i-th job.

We iterate over each job and for each job look backward in time to find a job that finishes before the current one starts, and hence does not conflict with the current job. bisect_right is the standard binary search method used to find that point efficiently rather than scanning all previous jobs linearly, saving valuable computation time.

The update rule for our DP table is straightforward: we compare the profit of taking the current job (which includes adding its profit to the best result from jobs that end before it starts) versus not taking it (meaning we stick with the best result up to the previous job). Choosing the better of these two options yields our dp value for the current job.

The last value in our DP table will contain the maximum profit achievable after considering all jobs.

Learn more about Binary Search, Dynamic Programming and Sorting patterns.

Solution Approach

The implementation of this problem utilizes a sorted list, binary search, and dynamic programming to calculate the maximum profit for scheduling non-overlapping jobs. Each step of the approach is essential for the efficiency and correctness of the solution:

1. Sorting Jobs: First, we pair each job's endTime, startTime, and profit together and sort these pairs based on their endTime. This is done to consider jobs by the order they finish. The sorting is achieved through the sorted function, which sorts the zipped lists of end times, start times, and profits.

   1jobs = sorted(zip(endTime, startTime, profit))

2. Dynamic Programming Table (dp): We define a DP table dp of size n+1, where n is the number of jobs to store the maximum profit up to each job. We initialize this table with zeros.

   1dp = [0] * (n + 1)

3. Binary Search: For each job, we need to find the closest job that finished before the current job's start. This is where bisect_right from the bisect module is used. It performs a binary search to find the insertion point of the current job’s start time in the sorted jobs array to ensure no overlap.

   1j = bisect_right(jobs, s, hi=i, key=lambda x: x[0])

   The callback lambda x: x[0] is used to ensure the search operates on the endTime of the jobs. j is the index where the job can be inserted without conflict, so dp[j] corresponds to the maximum profit up to the job that finishes right before the current job can start.

4. Profit Calculation: For every job at index i, we perform a calculation to determine the maximum profit including the current job versus excluding it. To include the current job, we take the profit of the current job p and add it to the profit accumulated until the closest non-conflicting job, which is dp[j]. If this sum is greater than the maximum profit without the current job dp[i], we update our dp at i+1 with this larger value; else, we carry over the maximum profit without the current job.

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

5. Result: After considering all jobs, the maximum profit that can be achieved is stored at the end of the dp array. Therefore, the last entry dp[n] is returned as the final result.

   1return dp[n]

By using these steps, the solution efficiently calculates the maximum profit without overlapping jobs by considering each job's contribution to the overall profit only if it adds value compared to the profit obtained without it. It balances between taking the new job or proceeding with the previously accumulated profit, resulting in an optimal scheduling strategy.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have the following set of jobs, with their respective start times, end times, and profits:

1start time: [1, 2, 3, 4]
2end time:   [3, 5, 6, 7]
3profit:     [50, 20, 100, 70]

There are 4 jobs to consider. Following the solution approach:

1. Sorting Jobs: We create job tuples (endTime, startTime, profit) and sort them by endTime as follows:

   1jobs = sorted(zip([3, 5, 6, 7], [1, 2, 3, 4], [50, 20, 100, 70]))
   2// After sorting -> [(3, 1, 50), (5, 2, 20), (6, 3, 100), (7, 4, 70)]

2. Dynamic Programming Table (dp): Here, n is 4, so dp will have 5 elements initialized to zero:

   1dp = [0, 0, 0, 0, 0]

3. Binary Search: As we compute the dp value for each job, we'll need the latest non-conflicting job, found using binary search:

   • For the first job (3, 1, 50), as it's the first there are no previous jobs, so dp[1] becomes 50.
   • For the second job (5, 2, 20), binary search (bisect_right) will find no non-conflicting job since it overlaps with the first job, hence dp[2] is max(dp[1], dp[0] + 20) which is 50.
   • For the third job (6, 3, 100), binary search will find the first job ends right before this one starts. So, dp[3] is max(dp[2], dp[1] + 100) which is 100.
   • For the fourth job (7, 4, 70), binary search again finds the second job ends right before this one starts. So, dp[4] is max(dp[3], dp[2] + 70) which is 120.

4. Profit Calculation: After processing all the jobs, our dp table looks like this:

   1dp = [0, 50, 50, 100, 120]

   This table reads as follows: The maximum profit up to (and including) each job index is recorded in dp. For instance, by the fourth job, the maximum profit we can have obtained is 120.

5. Result: The result of the contiguous job scheduling for this example is dp[4] which equals 120. This is the maximum profit we can earn without overlapping jobs. Therefore:

   1return dp[4]  # Outputs: 120

By applying these steps to the example, we efficiently calculate the maximum profit of 120 by scheduling the first and third jobs which do not overlap in time.

Solution Implementation

Time and Space Complexity

The given Python code defines a method for scheduling jobs to maximize profit, where each job has a start time, end time, and profit associated with it. The code uses dynamic programming to solve the problem and binary search to find the latest job end time that does not conflict with the current job's start time.

Time Complexity:

• Sorting the jobs by their end times at the beginning has a time complexity of O(N log N), where N is the number of jobs.

• Iterating through the sorted jobs and using bisect_right to perform binary search each have their own complexities:

  • The iteration itself is O(N).
  • The binary search inside the loop via bisect_right has a complexity of O(log i) for each iteration, where i is the current index in the loop (in the worst-case scenario, this is O(log N)).

The binary search is called N times within the loop, resulting in O(N log N) for all binary search calls. Combining the sorting and binary search complexities, the overall time complexity is O(N log N).

Space Complexity:

• The dp list has a space complexity of O(N).

• The jobs list has a space complexity of O(N), for it stores the zipped version of endTime, startTime, and profit, all of which are lists of length N.

The additional space for the variables i, s, p, j and the space for function calls is negligible. Thus, the total space complexity of the algorithm is O(N).

Combining time and space complexities, the code has a total time complexity of O(N log N) and a total space complexity of O(N).

Learn more about how to find time and space complexity quickly using problem constraints.