Java Recursion, Memoization TLE, Any Idea?
Hi, thinking as top down, looks me more intuitive. I implemented a solution by using recursion and memoization.  But I still get TLE. Do you have any idea?\n- S
Hi, thinking as top down, looks me more intuitive. I implemented a solution by using recursion and memoization.  But I still get TLE. Do you have any idea?\n- Sort the rides by start time\n- Iterate on the rides and you have 2 option: take or not take. (recursion)\n- Keep a variable previous end to check current ride can be take. (if start of current is smaller than prev end you cannot take)\n\n```\n\tpublic long maxTaxiEarnings(int n, int[][] rides) {\n        Arrays.sort(rides, (x1,x2) -> Integer.compare(x1[0], x2[0]));\n        int result = getMaxRidings(rides, 0, 0, new Integer[n+1]); \n        return result;\n    }\n    \n    private int getMaxRidings(int[][] rides, int i, int prevEnd, Integer[] memo) {\n        if(i>= rides.length)\n            return 0;\n        \n        int start = rides[i][0];\n        int end = rides[i][1];\n        int tip = rides[i][2];\n        \n        if(memo[prevEnd]!=null)\n            return memo[prevEnd];\n        \n        int result1 = Integer.MIN_VALUE;\n        if(prevEnd<=start) {   \n            int profit = end-start+tip;\n            result1 =  profit + getMaxRidings(rides, i+1, Math.max(prevEnd, end), memo);\n        }\n        int result2 = getMaxRidings(rides, i+1, prevEnd, memo);\n        \n        memo[prevEnd] = Math.max(result1, result2);\n        return memo[prevEnd];\n    }\n```
[]