Lessons learned
Learning: \n Why sort on endTime: to decide if a taxi has to be picked, I need the info of all taxis that ended before the current taxi\'s startTime. (Think rea
**Learning**: \n* **Why sort on endTime**: to decide if a taxi has to be picked, I need the info of all taxis that ended before the current taxi\'s startTime. (Think real life). So **all taxis with endTime before current taxi\'s endTime must be computed already**. Thus the requirement of sort on endTime\n* **Why Binary Search or Linear Search**: (continuation of above) ... but what if current taxi started before its previous taxi (or previous taxis) ended. So those taxis will no longer be valid prev states of current taxi. Thus BS or LS to get the last valid prev state for current taxi.\n\n**Code**:\n```\n// Iterative approach. For recursive approach, read https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/1476877/Lessons-learned\nclass Solution {\n    public long maxTaxiEarnings(int n, int[][] rides) {\n        Arrays.sort(rides, (a, b) -> a[1] - b[1]);\n        long[] dp = new long[rides.length];\n        Arrays.fill(dp, -1);\n        \n        dp[0] = getCost(rides[0]);\n        long ans = dp[0];\n        for (int i = 1; i < rides.length; ++i) {\n            \n            int prevState = bs(rides, i);\n            \n\t\t\t// IMP: Edge case 1\n            long prevStateCachedVal = prevState == -1 ? 0 : dp[prevState];\n\t\t\t\n\t\t\t// IMP: Edge case 2. Never forget to max with dp[i - 1]. Reason being what if there is a better answer for i - 1 but is not a valid prev of i. Then for future taxis, if current taxi is a valid prev, then we need the dp[i - 1] value.\n            // IMP: LIS doesn\'t have this. LIS has to scan all prev sates since search space is unsorted. Whlle here in Weighted Interval Scheduling search space is sorted. So for any current state, its first nearest valid prev state contains contribution of all the states behind this prev.\n            dp[i] = Math.max(prevStateCachedVal + getCost(rides[i]), dp[i - 1]); \n\t\t\t\n            ans = Math.max(ans, dp[i]);\n        }\n        \n        return ans;\n    }\n    \n    private long getCost(int[] ride) {\n        int start = ride[0];\n        int end = ride[1];\n        int tip = ride[2];\n        return end - start + tip;\n    }\n    \n    private int bs(int[][] rides, int currentTaxi) {\n        int start = 0, end = currentTaxi, nextIndex = -1;\n        \n        while (start <= end) {\n            int mid = (start + end) / 2;\n            if (rides[mid][1] <= rides[currentTaxi][0]) {\n                nextIndex = mid;\n                start = mid + 1;\n            } else {\n                end = mid - 1;\n            }\n        }\n        return nextIndex;\n    }\n}\n```
[]