#1235. Maximum Profit in Job Scheduling

I am still studying this answer I got from chatgpt. But it absolutely works.

https://leetcode.com/problems/maximum-profit-in-job-scheduling/?envType=daily-question&envId=2024-01-06

function jobScheduling(startTime, endTime, profit) {
    const jobs = [];
    const n = startTime.length;

    // Create a list of jobs as tuples [start, end, profit]
    for (let i = 0; i < n; i++) {
        jobs.push([startTime[i], endTime[i], profit[i]]);
    }

    // Sort the jobs based on their end times
    jobs.sort((a, b) => a[1] - b[1]);

    // Initialize an array to store the maximum profit at each job
    const dp = new Array(n).fill(0);
    dp[0] = jobs[0][2];

    // Binary search helper function to find the latest non-overlapping job
    function binarySearch(startIndex) {
        let low = 0, high = startIndex - 1;

        while (low <= high) {
            const mid = Math.floor((low + high) / 2);

            if (jobs[mid][1] <= jobs[startIndex][0]) {
                if (jobs[mid + 1][1] <= jobs[startIndex][0]) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }

    // Dynamic Programming to calculate maximum profit
    for (let i = 1; i < n; i++) {
        const inclProf = jobs[i][2];
        const l = binarySearch(i);

        if (l !== -1) {
            dp[i] = Math.max(inclProf + dp[l], dp[i - 1]);
        } else {
            dp[i] = Math.max(inclProf, dp[i - 1]);
        }
    }

    return dp[n - 1];
}