Maximum Profit in Job Scheduling

Try to solve the Maximum Profit in Job Scheduling problem.

We'll cover the following

Statement#

Suppose there are nn jobs, each with a start time, end time, and a corresponding profit. The goal is to schedule these jobs in a way that the sum of their profits is maximized while ensuring that no two jobs overlap in time. Given the arrays of start_time, end_time, and profit, calculate the maximum profit that can be obtained.

Note: Selecting a job that finishes at time tt means you can pick the next job that starts at the same time tt or later.

Constraints:

  • 1≤1 \leq start_time.length ==== end_time.length ==== profit.length ≤\leq 10310^3

  • 1≤1 \leq start_time[i] << end_time[i] ≤105\leq 10^5

  • 1≤1 \leq profit[i] ≤104\leq 10^4

Examples#

canvasAnimation-image

1 of 3

canvasAnimation-image

2 of 3

canvasAnimation-image

3 of 3


Understand the problem#

Maximum Profit in Job Scheduling

1

What is the output if the following start times, end times, and profits of some jobs are given as input?

start_time:  [1, 2, 3, 4]
end_time  :  [3, 4, 5, 6]
profit    :  [20, 10, 30, 40]
A)

60

B)

50

C)

40

D)

30

Question 1 of 30 attempted


Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Combine the input data into a single array of tuples, jobs, where each tuple contains the start time, end time, and associated profit of a job.

Sort the jobs array based on the end times of jobs in ascending order.

Iterate through the jobs array, and for each job, check whether it can be included in the schedule while maintaining non-overlapping time ranges.

Calculate the profit by including the current job, and by excluding the current job. Then, select the maximum of the two as the optimal profit for the current job.

After iterating all the jobs and considering various scheduling options, return the profit value against the schedule which yields the highest profit as the final answer.


Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
Input #3
%0 node_01 1 node_11 2 node_21 3
Visualization for Input #1
Maximum Profit in Job Scheduling

Solution: Word Break

Solution: Maximum Profit in Job Scheduling