Weighted Job Scheduling

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?