Weighted Job Scheduling

Problem Statement

Given n jobs where each job has a start time, end time, and profit. Find the maximum profit you can earn by scheduling non-overlapping jobs. Two jobs are non-overlapping if one ends before or when the other starts.

Example:

• Input: jobs = [(1,2,50), (3,5,20), (6,19,100), (2,100,200)] (start, end, profit)
• Output: 250
• Explanation: Pick job 1 (profit 50) and job 4 (profit 200) — they don't overlap (job 1 ends at 2, job 4 starts at 2). Total = 250.

Noob-Friendly Explanation

Imagine you're a freelancer and you get a bunch of job offers. Each job has a start date, end date, and how much money you'll earn. The problem is that some jobs overlap in time — you can't do two jobs at the same time. You want to pick the combination of jobs that earns you the most money without any time conflicts.

It's like picking which birthday parties to attend when some happen at the same time — you want to maximize the fun (here, the money)!

Approach 1: Brute Force (Recursion)

Intuition

Sort jobs by end time. For each job, decide to either include it or skip it. If we include a job, we skip all jobs that overlap with it.

Algorithm

1. Sort jobs by end time.
2. For each job, recursively try two options: include it (and skip conflicting jobs) or skip it.
3. Return the maximum profit.

import java.util.Arrays;

class Solution {
    int[][] jobs; // [start, end, profit]

    public int maxProfit(int[][] jobs) {
        this.jobs = jobs;
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]); // Sort by end time
        return solve(jobs.length - 1);
    }

    private int solve(int index) {
        if (index < 0) return 0;

        // Option 1: Skip this job
        int skip = solve(index - 1);

        // Option 2: Include this job
        // Find the latest job that doesn't conflict
        int prevJob = -1;
        for (int i = index - 1; i >= 0; i--) {
            if (jobs[i][1] <= jobs[index][0]) {
                prevJob = i;
                break;
            }
        }
        int include = jobs[index][2] + solve(prevJob);

        return Math.max(skip, include);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - At each step we branch into two choices.
• Space Complexity: O(n) - Recursion stack depth.

Approach 2: Optimal (DP + Binary Search)

Intuition

Sort jobs by end time and use DP. For each job, use binary search to quickly find the latest non-conflicting job instead of scanning linearly.

Algorithm

1. Sort jobs by end time.
2. Create a DP array where dp[i] = max profit considering jobs 0 to i.
3. For each job i, use binary search to find the latest job j that ends before job i starts.
4. dp[i] = max(dp[i-1], jobs[i].profit + dp[j]).

import java.util.Arrays;

class Solution {
    public int maxProfit(int[][] jobs) {
        int n = jobs.length;
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]); // Sort by end time

        int[] dp = new int[n];
        dp[0] = jobs[0][2];

        for (int i = 1; i < n; i++) {
            // Profit if we include this job
            int includeProfit = jobs[i][2];
            int lastNonConflict = binarySearch(jobs, i);
            if (lastNonConflict != -1) {
                includeProfit += dp[lastNonConflict];
            }

            // Max of including or excluding this job
            dp[i] = Math.max(dp[i - 1], includeProfit);
        }

        return dp[n - 1];
    }

    // Find the latest job that ends before or at jobs[index] start time
    private int binarySearch(int[][] jobs, int index) {
        int target = jobs[index][0];
        int lo = 0, hi = index - 1, result = -1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (jobs[mid][1] <= target) {
                result = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n log n) - Sorting takes O(n log n) and for each of the n jobs, binary search takes O(log n).
• Space Complexity: O(n) - DP array of size n.