Java | Time : O(n) | Space : O(n) | Dp
\n//Example\n//Input : [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]\n//Output : 20\n\n//1. Build map {key : end point, value : list of rides ends 
```\n//Example\n//Input : [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]\n//Output : 20\n\n//1. Build map {key : end point, value : list of rides ends at key}\n//{\n//(6, [1,6,1]),\n//(10,[3,10,2]),\n//(12,[10,12,3], [11,12,2]),\n//(15, [12,15,2]),\n//(18, [13,18,1])\n//}\n\n//2. Consider sub problems, what is the max earn till i (0<=i<=n) ?\n// we denote its value as dp[i]\n\n//3, eventually, we want to build up solution dp[i] from previous calculated \n// solutions to previous subproblems. => dp transition function\n// how do we know about this ? more examples ....\n\n//dp[0], dp[1], dp[2], dp[3], dp[4], dp[5], -> no possible passenger dropping, no gain\n\n// i = 6\n// dp[6] = Math.max(choice 1, choice 2)\n// choice 1 : we did not pick up passenger 1, dp[6] = dp[5] = 0\n// choice 2 : we picked up passenger 1, dp[6] = end_1 - start_1 + tip_1 = 6\n// dp[6] = Math.max(0, 6) = 6\n\n//dp[7], dp[8], dp[9] = dp[6] -> no possible passenger dropping, no gain, dp value remains\n\n// i = 10\n//dp[10] = Math.max(choice 1, choice 2)\n//choice 1 : we did not pick up passenger 2, dp[10] = dp[9] = 6\n//choice 2 : we picked up passenger 2, since passenger starts at i = 3, we have\n// dp[10] = dp[3] + gain from passenger 2 = 0 + 9 = 9\n// dp[10] = Math.max(6,9) = 9\n\n\n//dp[11] = dp[10] = 9\n\n//i = 12 (tricky one!!)\n//dp[12] = Math.max(choice 1, choice 2, choice 3)\n//choice 1 : we did not pick up any passenger end at i = 12, dp[12] = dp[11] = 9\n//choice 2 : we picked up passenger 3,\n// dp[12] = dp[10] + gain from passenger 3 = 9 + 5 = 14\n//choice 3 : we picked up passenger 4\n// dp[12] = dp[11] + gain from passenger 4 = 9 + 3 = 12\n//dp[12] = Math.max(choice 1, choice 2, choice 3) = 14\n\n// so.... I think you get the gist by far ..\n\n\n\n\nclass Solution {\n    public long maxTaxiEarnings(int n, int[][] rides) {\n        Map<Integer,List<int[]>> map = new HashMap<>();\n        for(int[] ride:rides){\n            map.putIfAbsent(ride[1],new ArrayList<int[]>());\n            map.get(ride[1]).add(ride);\n        }\n        long[] dp = new long[n+1];\n        for(int i=1;i<=n;i++){\n            dp[i] = dp[i-1];\n            if(map.containsKey(i)){\n                for(int[] r:map.get(i)){\n                    dp[i] = Math.max(dp[i],r[1]-r[0]+r[2]+dp[r[0]]);\n                }\n            }\n        }\n        return dp[n];\n    }\n}\n```
['Dynamic Programming']