# 2008. Maximum Earnings From Taxi
###### tags: `Leetcode` `Medium` `Greedy` `Intervals`
Link: https://leetcode.com/problems/maximum-earnings-from-taxi/description/
## 思路
### 思路一
如果像LIS那样用dp是不行的 内外层回圈遍历```rides``` 时间复杂度会变成$O(N^2)$
所以要用双指针 由于无法保证```rides[i][1]```随着```rides[i][0]```增长(也就是如果用```i```遍历array的每个```rides[i][0]``` 我们需要另外一个指针```j```遍历array的找到有哪些```j```满足```rides[i][0]>=rides[j][1]``` 这是无法用双指针实现的)

对于每个起始点来说我们有两种选择
一种是令```dp[i]=dp[i-1]```表明我们没有在时间i有客人
一种是我们找到所有在时间i放下客人的interval 分别算收益 取最大的就是```dp[i]```
### 思路二
和[1235. Maximum Profit in Job Scheduling](https://hackmd.io/mEcrQmsWTkeLAg3nXw22sA)一样
## Code
### 思路一

class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        Arrays.sort(rides, (a,b)->(a[1]-b[1]));
        long[] dp = new long[n+1];
        int j = 0;
        for(int i=1; i<=n; i++){
            dp[i] = dp[i-1];
            while(j<rides.length && rides[j][1]==i){
                dp[i] = Math.max(dp[i], dp[rides[j][0]]+rides[j][1]-rides[j][0]+rides[j][2]);
                j++;
            }
        }
        return dp[n];
    }
}

### 思路二

class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        Arrays.sort(rides, (a,b)->(a[1]-b[1]));
        TreeMap<Integer, Long> map = new TreeMap<>();
        map.put(0,(long)0);
        for(int[] ride:rides){
            long p = map.floorEntry(ride[0]).getValue()+ride[1]-ride[0]+ride[2];
            if(p>map.lastEntry().getValue()){
                map.put(ride[1], p);
            }
        }
        return map.lastEntry().getValue();
    }
}