Log inSign up
hardLeetCodeNot Started

Maximum Profit in Job Scheduling

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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 no two jobs in the subset have 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.

### Example 1 - Input: ``text 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 [1, 3] and [3, 6]) with profit 50 + 70 = 120`.

### Example 2 - Input: ``text startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] ` - **Output**: 150 - **Explanation**: Choose job 1, 4, and 5 (intervals [1,3], [4,6], [6,9]) with profit 20 + 70 + 60 = 150`.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Combine dynamic programming with binary search on intervals.
  • Understand the take / skip recurrence relation for weighted intervals.
  • Optimize state lookup from O(n) to O(log n).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Non-overlapping interval selection with weights/profits.
  • High constraint n = 50,000 -> O(n2) will TLE, requires O(n log n).

Algorithmic Decision Tree:

  • Group (startTime, endTime, profit) as a single job struct/tuple and sort.
  • Use binary search to locate non-overlapping next intervals.

Connected Patterns:

Non-overlapping IntervalsWeighted Job SchedulingLongest Increasing Subsequence

1. Recursive Pick / Skip with Linear Search

Intuition

Sort jobs and recursively decide whether to include job i or skip it, searching linearly for the next compatible job.

Algorithm

  1. Sort jobs by startTime.
  2. In solve(i):
  3. If i >= n, return 0.
  4. Option 1 (skip): solve(i + 1).
  5. Option 2 (take): Find first job j > i where startTime[j] >= endTime[i] by linear scan.
  6. Return max(Option 1, profit[i] + solve(j)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Job {
8 int start, end, profit;
9};
10
11class Solution {
12 int solve(int i, const vector<Job>& jobs) {
13 if (i >= jobs.size()) return 0;
14 // Skip
15 int skip = solve(i + 1, jobs);
16 // Take
17 int nextIdx = i + 1;
18 while (nextIdx < jobs.size() && jobs[nextIdx].start < jobs[i].end) {
19 nextIdx++;
20 }
21 int take = jobs[i].profit + solve(nextIdx, jobs);
22 return max(skip, take);
23 }
24public:
25 int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
26 int n = startTime.size();
27 vector<Job> jobs(n);
28 for (int i = 0; i < n; ++i) jobs[i] = {startTime[i], endTime[i], profit[i]};
29 sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
30 return a.start < b.start;
31 });
32 return solve(0, jobs);
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<int> s = {1, 2, 3, 3};
39 vector<int> e = {3, 4, 5, 6};
40 vector<int> p = {50, 10, 40, 70};
41 cout << "Max Profit: " << sol.jobScheduling(s, e, p) << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Memoized Top-Down DP with Linear Search

Intuition

Cache results of solve(i) in a memo table of size n.

Algorithm

  1. Initialize memo array of size n with -1.
  2. Check memo[i] before computing.
  3. Return memo[i] = max(skip, take).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Job { int start, end, profit; };
8
9class Solution {
10 int solve(int i, const vector<Job>& jobs, vector<int>& memo) {
11 if (i >= jobs.size()) return 0;
12 if (memo[i] != -1) return memo[i];
13 int skip = solve(i + 1, jobs, memo);
14 int nextIdx = i + 1;
15 while (nextIdx < jobs.size() && jobs[nextIdx].start < jobs[i].end) nextIdx++;
16 int take = jobs[i].profit + solve(nextIdx, jobs, memo);
17 return memo[i] = max(skip, take);
18 }
19public:
20 int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
21 int n = startTime.size();
22 vector<Job> jobs(n);
23 for (int i = 0; i < n; ++i) jobs[i] = {startTime[i], endTime[i], profit[i]};
24 sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) { return a.start < b.start; });
25 vector<int> memo(n, -1);
26 return solve(0, jobs, memo);
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> s = {1, 2, 3, 3};
33 vector<int> e = {3, 4, 5, 6};
34 vector<int> p = {50, 10, 40, 70};
35 cout << "Max Profit: " << sol.jobScheduling(s, e, p) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

3. DP with Binary Search (O(n log n))

Intuition

Sort jobs by start time. Use std::lower_bound (or bisect_left) to find the next job in O(log n) time per state.

Algorithm

  1. Sort jobs by startTime.
  2. Create a separate array of startTimes for binary search.
  3. Use memoization / bottom-up: for each job i:
  4. skip = dp[i + 1].
  5. next_idx = binary_search(startTimes, jobs[i].end).
  6. take = jobs[i].profit + (next_idx < n ? dp[next_idx] : 0).
  7. dp[i] = max(skip, take).
  8. Return dp[0].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Job {
8 int start, end, profit;
9};
10
11class Solution {
12public:
13 int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
14 int n = startTime.size();
15 vector<Job> jobs(n);
16 for (int i = 0; i < n; ++i) jobs[i] = {startTime[i], endTime[i], profit[i]};
17 sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
18 return a.start < b.start;
19 });
20
21 vector<int> starts(n);
22 for (int i = 0; i < n; ++i) starts[i] = jobs[i].start;
23
24 vector<int> dp(n + 1, 0);
25 for (int i = n - 1; i >= 0; --i) {
26 int skip = dp[i + 1];
27 // Binary search for next job where start >= current end
28 auto it = lower_bound(starts.begin(), starts.end(), jobs[i].end);
29 int nextIdx = distance(starts.begin(), it);
30 int take = jobs[i].profit + dp[nextIdx];
31 dp[i] = max(skip, take);
32 }
33
34 return dp[0];
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> s = {1, 2, 3, 3};
41 vector<int> e = {3, 4, 5, 6};
42 vector<int> p = {50, 10, 40, 70};
43 cout << "Max Profit: " << sol.jobScheduling(s, e, p) << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(n log n)
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Pick/SkipO(2^n)O(n)Exhaustive branching over all combinations.Overlapping subsets
2.Memoized DP with Linear SearchO(n^2)O(n)Memoize states i, linear scan to find next non-overlapping job.Linear scan per state
3.DP with Binary SearchOptimalO(n log n)O(n)Sort jobs and use binary search (bisect) for O(log n) next job transitions.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Confusing strictly greater with greater-or-equal: startTime >= endTime is allowed by problem statement.

Pitfall 2:

Sorting only startTime without keeping endTime and profit aligned.

Crucial Edge Cases to Validate:

  • Jobs can start right when another finishes: start == end is valid.
  • Single job: return its profit directly.
  • All jobs overlap: choose the single job with the maximum profit.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that this is the classic Weighted Interval Scheduling problem solved with DP + binary search.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we use binary search rather than a linear scan to find the next compatible job?

Back to DSA Sheet