Course4all
Join us on telegram
Home/dsa/Greedy/Weighted Job Scheduling

Weighted Job Scheduling

Master this topic with zero to advance depth.

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];
    }
}
← Previous QuestionMinimum Number of K Consecutive Bit Flips
Next Question →Course Schedule III