Most profit from jobs that do not overlap

from bisect import bisect_right

def max_profit_jobs(jobs):
    jobs = sorted(jobs, key=lambda j: j[1])        # by end time
    ends = [e for _, e, _ in jobs]
    best = [0]                                      # best[i]: most profit from the first i jobs
    for i, (s, e, p) in enumerate(jobs):
        k = bisect_right(ends, s, 0, i)             # jobs that end by s
        best.append(max(best[i], p + best[k]))      # skip it, or take it
    return best[-1]

#include <vector>
#include <algorithm>

long long solve(std::vector<std::vector<int>> jobs) {
    std::sort(jobs.begin(), jobs.end(), [](const std::vector<int>& a, const std::vector<int>& b) { return a[1] < b[1]; });
    std::vector<int> ends;
    for (const auto& j : jobs) ends.push_back(j[1]);
    std::vector<long long> best(jobs.size() + 1, 0);    // best[i]: most profit from the first i jobs
    for (size_t i = 0; i < jobs.size(); ++i) {
        // jobs among the first i that end by this job's start
        size_t k = std::upper_bound(ends.begin(), ends.begin() + i, jobs[i][0]) - ends.begin();
        best[i + 1] = std::max(best[i], jobs[i][2] + best[k]);   // skip it, or take it
    }
    return best.back();
}

class Solution {
    public long maxProfitJobs(int[][] jobs) {
        int[][] J = jobs.clone();
        java.util.Arrays.sort(J, (a, b) -> Integer.compare(a[1], b[1]));   // by end time
        int n = J.length;
        long[] best = new long[n + 1];                 // best[i]: most profit from the first i jobs
        for (int i = 0; i < n; i++) {
            int lo = 0, hi = i;                        // count earlier jobs with end <= start
            while (lo < hi) {
                int m = (lo + hi) >>> 1;
                if (J[m][1] <= J[i][0]) lo = m + 1; else hi = m;
            }
            best[i + 1] = Math.max(best[i], J[i][2] + best[lo]);   // skip it, or take it
        }
        return best[n];
    }
}

function maxProfitJobs(jobs) {
  const J = jobs.map(j => j.slice()).sort((a, b) => a[1] - b[1]);   // by end time
  const ends = J.map(j => j[1]);
  const best = [0];                                // best[i]: most profit from the first i jobs
  J.forEach(([s, , p], i) => {
    let lo = 0, hi = i;                            // count earlier jobs with end <= s
    while (lo < hi) {
      const m = (lo + hi) >> 1;
      if (ends[m] <= s) lo = m + 1; else hi = m;
    }
    best.push(Math.max(best[i], p + best[lo]));    // skip it, or take it
  });
  return best[J.length];
}

fn solve(jobs: &[[i64; 3]]) -> i64 {
    let mut j = jobs.to_vec();
    j.sort_by_key(|x| x[1]);                       // by end time
    let ends: Vec<i64> = j.iter().map(|x| x[1]).collect();
    let mut best = vec![0i64; j.len() + 1];        // best[i]: most profit from the first i jobs
    for i in 0..j.len() {
        let k = ends[..i].partition_point(|&e| e <= j[i][0]);   // earlier jobs that end by the start
        best[i + 1] = best[i].max(j[i][2] + best[k]);           // skip it, or take it
    }
    best[j.len()]
}

import Data.List (sortOn)
import qualified Data.Map.Strict as M

-- Sort by end time; best maps each end time to the most profit achievable by then.
-- For each job, look up the best total among jobs ending by its start (lookupLE).
solve :: [[Int]] -> Int
solve jobs = snd (M.findMax final)
  where
    final = foldl step (M.singleton minBound 0) (sortOn (!! 1) jobs)
    step best [s, e, p] =
      let upto  = maybe 0 snd (M.lookupLE s best)     -- best schedule finished by s
          sofar = snd (M.findMax best)                -- best schedule so far (skip this job)
      in M.insert e (max sofar (p + upto)) best