#1235

Maximum Profit in Job Scheduling

candidate master · 1300 · lc hard +32 · verified · 54.6% accepted · 7,281 likes · top 47%

Description

You have n jobs. Job i runs from startTime[i] to endTime[i] and earns profit[i]. Select a non-overlapping subset of jobs to maximize total profit.

Given startTime, endTime, and profit arrays, return the maximum profit achievable with no two selected jobs having overlapping time ranges.

A job ending at time X allows another to start at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

Output: 120

Explanation: The subset chosen is the first and fourth job.

Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

Output: 150

Explanation: The subset chosen is the first, fourth and fifth job.

Profit obtained 150 = 20 + 70 + 60.

Example 3:

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

Output: 6

Code

1

2

3

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int: