Course4all

Weighted Job Scheduling

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Greedy.

Weighted Job Scheduling

Find maximum profit from non-overlapping jobs with given startTime, endTime, and profit.

Visual Representation

Jobs (S, E, P): J1: [1, 3, 50], J2: [2, 4, 10], J3: [3, 5, 40], J4: [3, 6, 70] Combination J1 (50) + J4 (70) = 120 (Max)
Hard

Examples

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
The subset of jobs [J1, J4] gives maximum profit.
Approach 1

Level I: Recursive Backtracking

Intuition

Try all possible subsets of compatible jobs and return the maximum profit. To handle compatibility, we sort by start time and at each step, decide to either pick the current job and skip all overlapping ones, or skip the current job.

Thought Process

  1. solve(idx): Max profit starting from job idx.
  2. Decision 1: Skip job idx -> solve(idx + 1).
  3. Decision 2: Pick job idx. Find the next job k > idx that starts after jobs[idx].end. Result = profit[idx] + solve(k).
  4. Return max(Decision 1, Decision 2).
⏱ O(2^N).💾 O(N)

Detailed Dry Run

Jobs: [1,3,50], [2,4,10], [3,5,40]
  1. solve(0):
    • Skip J1: solve(1)
    • Pick J1: 50 + solve(2) (J3 starts at 3, J1 ends at 3). Result = 50 + 40 = 90.
  2. Return 90.
java
public class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        return solve(0, jobs);
    }
    private int solve(int idx, int[][] jobs) {
        if (idx == jobs.length) return 0;
        // Skip
        int res = solve(idx + 1, jobs);
        // Pick
        int next = idx + 1;
        while (next < jobs.length && jobs[next][0] < jobs[idx][1]) next++;
        res = Math.max(res, jobs[idx][2] + solve(next, jobs));
        return res;
    }
}
Approach 2

Level II: Dynamic Programming (O(N^2))

Intuition

This is a variation of the Longest Increasing Subsequence (LIS) problem. For each job i, we look at all previous jobs j < i and if they are compatible, we update dp[i] = max(dp[i], dp[j] + profit[i]).

Thought Process

  1. Sort jobs by end time.
  2. dp[i] = max profit ending at job i.
  3. For each i, iterate all j < i and check if jobs[j].end <= jobs[i].start.
  4. This approach is O(N2)O(N^2) and will pass for medium constraints but TLE for N=105N=10^5.
⏱ O(N^2).💾 O(N).

Detailed Dry Run

Jobs: [J1:1-3, 50], [J2:2-4, 10], [J3:3-5, 40]
  1. dp[0] = 50 (J1)
  2. dp[1] = 10 (J2). J1 overlaps with J2.
  3. dp[2] = 40 + dp[0] = 90. J1 is compatible with J3. Max Profit = 90.
java
public class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]);
        int[] dp = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = jobs[i][2];
            for (int j = 0; j < i; j++) {
                if (jobs[j][1] <= jobs[i][0]) dp[i] = Math.max(dp[i], dp[j] + jobs[i][2]);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
Approach 3

Level III: Optimal (DP + Binary Search)

Intuition

Sort by end time. For each job, the max profit is either excluding it (same as max profit of previous job) or including it (profit + max profit of latest compatible job).

Thought Process

  1. Combine data and sort by endTime.
  2. dp[i] = max profit for first i jobs.
  3. Search for the latest job j < i where jobs[j].end <= jobs[i].start using binary search.
  4. dp[i] = max(dp[i-1], job[i].profit + dp[j]).

Pattern: Dynamic Programming + Binary Search

⏱ O(N log N) for sorting and binary searching.💾 O(N) for DP array.

Detailed Dry Run

Sorted: [J1:[1,3,50], J2:[2,4,10], J3:[3,5,40], J4:[3,6,70]] J1: dp[0]=50 J2: j=-1, dp[1]=max(50, 10)=50 J3: j=0, dp[2]=max(50, 40+50)=90 J4: j=0, dp[3]=max(90, 70+50)=120
java
public class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]);
        int[] dp = new int[n];
        dp[0] = jobs[0][2];
        for (int i = 1; i < n; i++) {
            int cur = jobs[i][2];
            int l = 0, r = i - 1, idx = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (jobs[mid][1] <= jobs[i][0]) { idx = mid; l = mid + 1; }
                else r = mid - 1;
            }
            if (idx != -1) cur += dp[idx];
            dp[i] = Math.max(dp[i - 1], cur);
        }
        return dp[n - 1];
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMinimum Number of K Consecutive Bit Flips
Next Question →Course Schedule III