class Solution { public int jobScheduling(int[] st, int[] ed, int[] pt) { // 按照结束时间排序，然后dp ; // dp[i] : 前i个工作结束的最大酬劳 // 不选i : dp[i] = dp[i-1] ; // 选i : dp[i] = dp[j]+profit[i] (ed[j]<=st[i]) // so : dp[i] = max(dp[i-1],dp[j]+pt[i]) ; int n = st.length ; int[][] jobs = new int[n][] ; for(int i=0;i<n;i++){ jobs[i] = new int[]{ed[i],st[i],pt[i]} ; } Arrays.sort(jobs,(a,b)->a[0]-b[0]) ; int[] dp = new int[n+1] ; dp[0] = 0 ; for(int i=0;i<n;i++){ int j = ef(jobs,i,jobs[i][1]) ; dp[i+1] = Math.max(dp[i],dp[j+1]+jobs[i][2]) ; } return dp[n] ; } // 查找ed<=m的最大下标 private int ef(int[][] jobs,int r,int m){ int l = -1 ; // ***二分 while(l+1<r){ int mid = (l+r)/2 ; if(jobs[mid][0]<=m) l = mid ; else r = mid ; } return l ; } }