Log inSign up
hardGeeksforGeeksNot Started

Weighted Job Scheduling

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

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given n jobs where every job is represented by a start time, finish time, and profit associated with it. Find the maximum profit subset of non-overlapping jobs.

Two jobs are considered overlapping if one starts before the other ends (i.e. start time of second job < finish time of first job). If a job finishes at time X, another job can start at time X.

### Example 1 - Input: jobs = [[1, 2, 50], [3, 5, 20], [6, 19, 100], [2, 100, 200]] - Output: 250 - Explanation: We can select jobs [1, 2, 50] and [2, 100, 200] to get total profit 50 + 200 = 250.

### Example 2 - Input: jobs = [[1, 3, 20], [2, 5, 20], [3, 10, 100], [4, 6, 70], [6, 9, 60]] - Output: 150 - Explanation: Select [1, 3, 20], [4, 6, 70], and [6, 9, 60] for 20 + 70 + 60 = 150 (or [2, 5, 20] and others). Maximum is 150.

Constraints:

  • 1 <= n <= 5 * 104
  • 1 <= start < finish <= 109
  • 1 <= profit <= 104

What You'll Learn

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

  • Formulate weighted interval scheduling via dynamic programming.
  • Use binary search over sorted finish times.
  • Implement 1D DP tabulation achieving optimal O(n log n) runtime.

Pattern Recognition Trigger

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

Signals to Look For:

  • Non-overlapping interval scheduling with weights.
  • Large constraint n up to 50,000 requiring O(n log n).

Algorithmic Decision Tree:

  • Sort by finish time to enable prefix DP.
  • Use upper_bound / bisect_right on finish times.

Connected Patterns:

Maximum Profit in Job SchedulingNon-overlapping IntervalsLongest Increasing Subsequence

1. Recursive Inclusion / Exclusion with Linear Scan

Intuition

Sort jobs by finish time and recursively evaluate include vs exclude with a linear scan for non-conflicting jobs.

Algorithm

  1. Sort jobs by finish time.
  2. Define solve(i).
  3. If i < 0, return 0.
  4. Exclude: solve(i - 1).
  5. Include: Find latest j < i with jobs[j].finish <= jobs[i].start via linear scan.
  6. Return max(exclude, jobs[i].profit + solve(j)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Job { int start, finish, profit; };
8
9class Solution {
10 int solve(int i, const vector<Job>& jobs) {
11 if (i < 0) return 0;
12 int exclude = solve(i - 1, jobs);
13
14 int latest = -1;
15 for (int j = i - 1; j >= 0; --j) {
16 if (jobs[j].finish <= jobs[i].start) {
17 latest = j;
18 break;
19 }
20 }
21 int include = jobs[i].profit + solve(latest, jobs);
22 return max(exclude, include);
23 }
24public:
25 int maxProfit(vector<vector<int>>& jobList) {
26 int n = jobList.size();
27 vector<Job> jobs(n);
28 for (int i = 0; i < n; ++i) jobs[i] = {jobList[i][0], jobList[i][1], jobList[i][2]};
29 sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
30 return a.finish < b.finish;
31 });
32 return solve(n - 1, jobs);
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<vector<int>> jobs = {{1, 2, 50}, {3, 5, 20}, {6, 19, 100}, {2, 100, 200}};
39 cout << "Max Profit: " << sol.maxProfit(jobs) << endl;
40 return 0;
41}

Time & Space Complexity

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

2. Memoized DP with Linear Scan (O(n^2))

Intuition

Cache results of solve(i) in a memo array of size n, finding the previous non-overlapping job linearly.

Algorithm

  1. Initialize memo array of size n with -1.
  2. In solve(i): return memo[i] if already computed.
  3. Linear scan to find latest non-conflicting job.
  4. Store and return memo[i] = max(exclude, include).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Job { int start, finish, profit; };
8
9class Solution {
10 int solve(int i, const vector<Job>& jobs, vector<int>& memo) {
11 if (i < 0) return 0;
12 if (memo[i] != -1) return memo[i];
13
14 int exclude = solve(i - 1, jobs, memo);
15 int latest = -1;
16 for (int j = i - 1; j >= 0; --j) {
17 if (jobs[j].finish <= jobs[i].start) {
18 latest = j;
19 break;
20 }
21 }
22 int include = jobs[i].profit + solve(latest, jobs, memo);
23 return memo[i] = max(exclude, include);
24 }
25public:
26 int maxProfit(vector<vector<int>>& jobList) {
27 int n = jobList.size();
28 vector<Job> jobs(n);
29 for (int i = 0; i < n; ++i) jobs[i] = {jobList[i][0], jobList[i][1], jobList[i][2]};
30 sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) { return a.finish < b.finish; });
31 vector<int> memo(n, -1);
32 return solve(n - 1, jobs, memo);
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<vector<int>> jobs = {{1, 2, 50}, {3, 5, 20}, {6, 19, 100}, {2, 100, 200}};
39 cout << "Max Profit: " << sol.maxProfit(jobs) << endl;
40 return 0;
41}

Time & Space Complexity

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

3. Iterative 1D DP with Binary Search (O(n log n))

Intuition

Sort jobs by finish time. Use binary search (upper_bound / bisect) to find the latest non-conflicting job in O(log n) time per state.

Algorithm

  1. Sort jobs by finish time.
  2. Initialize dp array of size n with 0.
  3. dp[0] = jobs[0].profit.
  4. For i from 1 to n - 1:
  5. incl = jobs[i].profit.
  6. Use binary search to find latest l < i where jobs[l].finish <= jobs[i].start.
  7. If l != -1, incl += dp[l].
  8. dp[i] = max(dp[i - 1], incl).
  9. Return dp[n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Job { int start, finish, profit; };
8
9class Solution {
10 int binarySearch(const vector<Job>& jobs, int index) {
11 int low = 0, high = index - 1, ans = -1;
12 while (low <= high) {
13 int mid = low + (high - low) / 2;
14 if (jobs[mid].finish <= jobs[index].start) {
15 ans = mid;
16 low = mid + 1;
17 } else {
18 high = mid - 1;
19 }
20 }
21 return ans;
22 }
23public:
24 int maxProfit(vector<vector<int>>& jobList) {
25 int n = jobList.size();
26 vector<Job> jobs(n);
27 for (int i = 0; i < n; ++i) jobs[i] = {jobList[i][0], jobList[i][1], jobList[i][2]};
28 sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
29 return a.finish < b.finish;
30 });
31
32 vector<int> dp(n, 0);
33 dp[0] = jobs[0].profit;
34
35 for (int i = 1; i < n; ++i) {
36 int incl = jobs[i].profit;
37 int l = binarySearch(jobs, i);
38 if (l != -1) incl += dp[l];
39 dp[i] = max(dp[i - 1], incl);
40 }
41
42 return dp[n - 1];
43 }
44};
45
46int main() {
47 Solution sol;
48 vector<vector<int>> jobs = {{1, 2, 50}, {3, 5, 20}, {6, 19, 100}, {2, 100, 200}};
49 cout << "Max Profit: " << sol.maxProfit(jobs) << endl;
50 return 0;
51}

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 SearchO(2^n)O(n)Exhaustive branching over inclusion/exclusion.Overlapping subproblems
2.Memoized DP + Linear ScanO(n^2)O(n)Cache states with linear scan for non-conflict.Linear scan per state
3.DP with Binary SearchOptimalO(n log n)O(n)Sort jobs by finish time, binary search for latest non-conflicting job.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Confusing strictly greater with greater-or-equal (finish <= start is permitted).

Pitfall 2:

Sorting only start times and attempting prefix DP without monotonic finish times.

Crucial Edge Cases to Validate:

  • Single job: Returns profit of that single job.
  • Non-overlapping contiguous jobs (e.g. [1, 2], [2, 3]): Valid since finish == start is non-conflicting.
  • All jobs completely overlapping: Returns max profit among individual jobs.

Interview Tips & Best Practices

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

  1. State that this is the classic Weighted Interval Scheduling problem presented in algorithm textbooks like Kleinberg & Tardos.

Quick Comprehension Check

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

1.Why do we sort jobs by FINISH time rather than start time in the optimal prefix DP solution?

Back to DSA Sheet