Dynamic Programming/Maximum Profit in Job SchedulingMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Maximum Profit in Job Scheduling

Dynamic Programming·Medium

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays. Return the maximum profit you can take such that there are no two jobs in the subset with overlapping time ranges.

If you choose a job that ends at time X you will be able to start another job that starts at time X (touching is allowed).

Standard approach: sort jobs by end time, and for each job binary-search the latest non-overlapping previous job. dp[i] = max(dp[i-1], profit[i] + dp[lastNonOverlap]).

Examples

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

Output: 120

Take jobs 0 (1-3, 50) and 3 (3-6, 70).

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

Output: 150

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

Output: 6

Constraints

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Dynamic Programming
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.