Coding

Maximum Profit in Job Scheduling

Asked at

Adobe

PhonePe

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given n jobs, where every job is represented by:

startTime[i]: the start time of the job,
endTime[i]: the end time of the job,
profit[i]: the profit earned from completing the job.

You cannot take two jobs that overlap in time.

Return the maximum profit you can earn such that there are no two overlapping jobs in your selected subset.

Note: A job ending at time X is allowed to overlap with another job that starts exactly at time X.

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

Select jobs [0, 3] with intervals [1-3] and [3-6].
Profit = 50 + 70 = 120.

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

Select jobs [0, 3, 4]: [1-3], [4-6], [6-9]
Total profit = 20 + 70 + 60 = 150.

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

1 <= startTime.length == endTime.length == profit.length <= 5 * 104
1 <= startTime[i] < endTime[i] <= 109
1 <= profit[i] <= 104

cpp

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        // Your code goes here
    }
};

java

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // Your code goes here
    }
}

python

class Solution:
    def jobScheduling(self, startTime, endTime, profit):
        # Your code goes here

javascript

function jobScheduling(startTime, endTime, profit) {
    // Your code goes here
}

csharp

class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // Your code goes here
    }
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {

Stuck? Show a way to structure it+

01Sort jobs by end time.
02Define dp[i] as best profit through i jobs.
03Binary-search the last compatible earlier job.
04Choose between skipping or taking the current job.
05Return the final DP value.

Reference answer

Sort jobs by end time so every compatible predecessor of job i lies earlier. Let dp[i] be the maximum profit from the first i sorted jobs. For the current job, binary-search the rightmost earlier end time <= start; call its one-based DP index p. Then dp[i] = max(dp[i-1], profit[i] + dp[p]): either skip this job or take it and append the best compatible schedule. Precompute an array of end times so predecessor lookup is logarithmic. Be explicit whether touching endpoints is compatible; this problem normally allows end <= start. Sorting costs O(N log N), the N predecessor searches cost O(N log N), and DP storage is O(N). This is weighted interval scheduling, not greedy interval selection.

Then expect these follow-ups

How would you reconstruct selected jobs?
Tests: DP reconstruction
Can you use recursion with memoization?
Tests: equivalent formulations

Hiring now

Adobe has 203 open roles right now

Also hiring: PhonePe

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

2027 Intern - Solutions Consulting
Paris
2027 Intern - Communications
San Francisco
Adobe Intern FY27
Bangalore

Or practice this question first

Next question