2008. 出租车的最大盈利 (opens new window)

1.二分+动规+排序

定义dp[ i ]表示前i个乘客内，能够获得的最大盈利。而不能以一定搭载第i个乘客的盈利定义。

• 首先对rides按照下车点递增排序
• 求解dp[ i ]时，对于第i个乘客有两种情况：
  • 载客第i个乘客：需要通过二分，找到0 ~ i内下车点小于等于当前乘客上车点的“最靠近”乘客。
  • 不载客第i个乘客：此时能够获盈利为dp[ i-1 ]

这里能够只用二分的结果dp[mid]+currPrice来更新当前dp[i]的原因有两点：

• 排过序后，前0到mid的乘客的下车点，肯定都满足小于当前第i个乘客的上车点
• 根据dp定义，dp[mid]必定大于等于前0 - mid-1的结果，因此只需要用mid更新一次即可。

class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
       Arrays.sort(rides, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]!=o2[1]) return o1[1] - o2[1];
                else return o1[0] - o2[0];
            }
        });
        long res = 0;
        long[] dp = new long[rides.length];
        for (int i = 0; i < rides.length; i++) {
            int pre = i - 1;
            int price = rides[i][1] - rides[i][0] + rides[i][2];
            //二分找到上一个最接近地点
            int left=0,right = i;
            while (left < right) {
                int mid = (left + right) >> 1;
                if(rides[mid][1]<=rides[i][0]) left=mid+1;
                else right = mid;
            }
            if(left-1>=0&&rides[left-1][1]<=rides[i][0]) dp[i] = Math.max(dp[i-1], dp[left-1] + price);
            else dp[i] = Math.max(i-1>=0?dp[i-1]:0, price);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}