Maximum Profit in Job Scheduling

class Solution {
public:
    int jobScheduling(vector<int>& s, vector<int>& e, vector<int>& p) {
        int n = s.size();
        vector<tuple<int,int,int>> jobs(n);
        for (int i = 0; i < n; ++i) jobs[i] = {e[i], s[i], p[i]};
        sort(jobs.begin(), jobs.end());
        vector<int> ends(n);
        for (int i = 0; i < n; ++i) ends[i] = get<0>(jobs[i]);
        vector<int> dp(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            auto [end, start, profit] = jobs[i];
            int j = upper_bound(ends.begin(), ends.begin() + i, start) - ends.begin();
            // j is count of jobs with end <= start; their best is dp[j]
            dp[i + 1] = max(dp[i], dp[j] + profit);
        }
        return dp[n];
    }
};

import "sort"

func jobScheduling(s []int, e []int, p []int) int {
    n := len(s)
    type job struct{ end, start, profit int }
    jobs := make([]job, n)
    for i := 0; i < n; i++ {
        jobs[i] = job{e[i], s[i], p[i]}
    }
    sort.Slice(jobs, func(i, j int) bool { return jobs[i].end < jobs[j].end })
    ends := make([]int, n)
    for i := 0; i < n; i++ {
        ends[i] = jobs[i].end
    }
    dp := make([]int, n+1)
    for i := 0; i < n; i++ {
        // upper_bound: first index with ends[idx] > start
        lo, hi := 0, i
        target := jobs[i].start
        for lo < hi {
            mid := (lo + hi) / 2
            if ends[mid] <= target {
                lo = mid + 1
            } else {
                hi = mid
            }
        }
        take := dp[lo] + jobs[i].profit
        if take > dp[i] {
            dp[i+1] = take
        } else {
            dp[i+1] = dp[i]
        }
    }
    return dp[n]
}

import bisect
from typing import List

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        jobs = sorted(zip(endTime, startTime, profit))
        ends = [j[0] for j in jobs]
        dp = [0] * (n + 1)
        for i in range(n):
            end, start, p = jobs[i]
            j = bisect.bisect_right(ends, start, 0, i)
            dp[i + 1] = max(dp[i], dp[j] + p)
        return dp[n]

function jobScheduling(startTime, endTime, profit) {
    const n = startTime.length;
    const jobs = [];
    for (let i = 0; i < n; i++) jobs.push([endTime[i], startTime[i], profit[i]]);
    jobs.sort((a, b) => a[0] - b[0]);
    const ends = jobs.map(j => j[0]);
    const dp = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        const [, start, p] = jobs[i];
        // upper_bound: first index with ends[idx] > start
        let lo = 0, hi = i;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (ends[mid] <= start) lo = mid + 1;
            else hi = mid;
        }
        dp[i + 1] = Math.max(dp[i], dp[lo] + p);
    }
    return dp[n];
}

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][0] = endTime[i];
            jobs[i][1] = startTime[i];
            jobs[i][2] = profit[i];
        }
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) ends[i] = jobs[i][0];
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int start = jobs[i][1];
            int p = jobs[i][2];
            // upper_bound: first index with ends[idx] > start
            int lo = 0, hi = i;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (ends[mid] <= start) lo = mid + 1;
                else hi = mid;
            }
            dp[i + 1] = Math.max(dp[i], dp[lo] + p);
        }
        return dp[n];
    }
}

function jobScheduling(startTime: number[], endTime: number[], profit: number[]): number {
    const n = startTime.length;
    const jobs: [number, number, number][] = [];
    for (let i = 0; i < n; i++) jobs.push([endTime[i], startTime[i], profit[i]]);
    jobs.sort((a, b) => a[0] - b[0]);
    const ends: number[] = jobs.map(j => j[0]);
    const dp: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        const [, start, p] = jobs[i];
        // upper_bound: first index with ends[idx] > start
        let lo = 0, hi = i;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (ends[mid] <= start) lo = mid + 1;
            else hi = mid;
        }
        dp[i + 1] = Math.max(dp[i], dp[lo] + p);
    }
    return dp[n];
}