🤯1235 max profit in job scheduling

https://leetcode.com/problems/maximum-profit-in-job-scheduling/

理解题意，大概就是你尽可能安排job，但是不一定所有job都要安排上，找出一种安排使得利润最大，这里有个暗含的限制条件是一旦你把job按照开始时间sort之后，你最终安排的jobs，第i个位置要么空着要么是第i个job，没有其他可能，理解这一点dp就有思路了

同时注意dp是从最后一个job倒推过来，我怀疑从前往后也是可以的？dp的含义是从第i个位置往后的总的最大利润，具体看注释，同时注意找nextjob的时候要用binary search来防止超时

class Solution {
    int[] dp;
    class Job implements Comparable<Job> {
        int start;
        int end;
        int profit;
        public Job(int s, int e, int p) {
            start = s;
            end = e;
            profit = p;
        }
        @Override
        public int compareTo(Job a) {
            return this.start - a.start;
        }
    }
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // you don't have to use all the jobs
        Job[] jobs = new Job[startTime.length];
        for (int i = 0; i < startTime.length; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        // sort jobs by starting time
        Arrays.sort(jobs);
        // in the ith position you can either put the ith job or not, you cannot put other job
        // since they start either earlier or later
        // dp[i] is the max profit from the ith job position to the end you can get
        // there are several situations:
        // 1. you put the ith job in it, and you find other jobs that can be put after it
        // 2. you put the ith job in it, and you find no other jobs that can be put after it
        // 3. you skip this job, don't put the ith job in the ith position
        dp = new int[startTime.length];
        findProfit(jobs);
        return dp[0];
    }
    private void findProfit(Job[] jobs) {
        int n = jobs.length;
        for(int i = n - 1; i >= 0; i--) {
            int profit = 0;
            // find the next job's index that can be put after current job and closest to current job
            // if index is length, then no job can be put after this job
            int nextJob = findNextJob(jobs, jobs[i].end);
            if (nextJob == n) {
                // if we insist on putting this job even though it makes no job being able to put after it
                // the max profit from this job on we get is just the profit of this job
                profit = jobs[i].profit;
            } else {
                profit = jobs[i].profit + dp[nextJob];
            }
            
            if (i == n - 1) {
                //we start from position = n which is our base case 
                // because when there are no more jobs to schedule the maximum profit must be 0
                dp[i] = profit;
            } else {
                // if we make more profit not putting this job, we don't put it, just skip ith
                dp[i] = Math.max(dp[i + 1], profit);
            }
        }
    }
    private int findNextJob(Job[] jobs, int end) {
        int n = jobs.length;
        int l = 0;
        int r = n - 1;
        while (l + 1 < r) {
            int m = l + (r - l) / 2;
            if (jobs[m].start >= end) {
                r = m;
            } else {
                l = m;
            }
        }
        if (jobs[l].start >= end) return l;
        if (jobs[r].start >= end) return r;
        return n;
    }
}