Weighted Job Scheduling

Problem Overview

DP on jobs sorted by end time.

See our study guide for structured GFG and LeetCode practice.

Intuition

DP on jobs sorted by end time. dp[i] = max profit using jobs from 1..i. Either take job i (binary search for last compatible job) or skip.

Algorithm

1Sort jobs by end time.
2dp[i] = max(dp[i-1], profit[i] + dp[last_compatible_job]).
3Binary search for last job ending <= start[i].

Common Pitfalls

• Job i is compatible with job j if end[j] <= start[i]. Binary search on sorted end times.

Weighted Job Scheduling.java

Java

// Approach: Sort by end time. DP: dp[i] = max weight inc. job i + dp[latest non-conflicting job]. Binary search for that.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    public int maxProfit(int[][] jobs) {
        Arrays.sort(jobs, (j1, j2) -> j1[1] - j2[1]);
        int n = jobs.length;
        int dp[] = new int[n];

        int ans = 0;

        for (int i = 0; i < n; i++) {
            int s = 0, e = i;
            while (s <= e) {
                int m = (s + e) / 2;
                if (jobs[m][1] <= jobs[i][0])
                    s = m + 1;
                else
                    e = m - 1;
            }
            
            int cur = jobs[i][2];
            if (e != -1)
                cur += dp[e];

            if (ans < cur)
                ans = cur;
            dp[i] = ans;

        }
        return ans;
    }
}

Was this solution helpful?