Java Brute force, dp (3 approaches) 2 TLE 1 AC
Approach 1:\n\nbrute force(take the ride or not)(TLE)\n\nclass Solution {\n    HashMap<Integer,List<int[]>> map = new HashMap();\n    public long maxTaxiEarning
Approach 1:\n\nbrute force(take the ride or not)(TLE)\n```\nclass Solution {\n    HashMap<Integer,List<int[]>> map = new HashMap();\n    public long maxTaxiEarnings(int n, int[][] rides) {\n        create(n,rides);\n        \n     \n        return f(1,n);\n    }\n    public long f(int start,int end){\n        if(start==end)\n            return 0;\n        long max=0;\n        for(int i=start;i<=end;i++){\n            if(map.containsKey(i))\n                for(int j=0;j<map.get(i).size();j++)\n            max=Math.max(max,f(map.get(i).get(j)[1],end)+map.get(i).get(j)[0]);\n        }\n        return max;\n    }\n    public void create(int n,int rides[][]){\n        for(int[] eachRide : rides)\n            if(!map.containsKey(eachRide[0]))\n            {    List<int[]> myList =new ArrayList();\n                 myList.add(new int[]{eachRide[1]-eachRide[0]+eachRide[2],eachRide[1]});\n                map.put(eachRide[0],myList);\n                     }\n        else{\n            List<int[]> myList =map.get(eachRide[0]);\n            myList.add(new int[]{eachRide[1]-eachRide[0]+eachRide[2],eachRide[1]});\n        }\n    }\n}\n\n```\n\n\n\nApproach 2:(A better DP)(TLE)(can be optimized by priority queue**)\n```\nclass Solution {\n long []dp;\n    \n    public long maxTaxiEarnings(int n, int[][] rides) {\n        \n        Arrays.sort(rides,(a,b)->{\n            return a[0]-b[0];\n        });\n        dp= new long[n+1];\n        for(int[] each : rides){\n            long value=dp[each[0]]+each[1]-each[0]+each[2];\n            for(int i=each[1];i<=n;i++){\n                dp[i]=Math.max(dp[i],value);\n                \n            }\n            \n        }\n return dp[n];\n    }\n    \n}`\n```\n\nApproach 3:(knapsack like appraoch taken from https://leetcode.com/problems/maximum-earnings-from-taxi/discuss/1470941/JavaC%2B%2BPython-DP-solution )\n\n```\nclass Solution {\n public long maxTaxiEarnings(int n, int[][] A) {\n        Arrays.sort(A, (a, b) -> a[0] - b[0]);\n        long[] dp = new long[n + 1];\n     int j=0;\n     for(int i=1;i<=n;i++){\n         dp[i]=Math.max(dp[i],dp[i-1]);\n         while(j<A.length && A[j][0]==i){\n             dp[A[j][1]]=Math.max(dp[A[j][1]],dp[i]-A[j][0]+A[j][1]+A[j][2]);\n             \n             \n             j++;\n         }\n         \n         \n     }\n     return dp[n];\n \n    }\n    \n}\n```\n\ncomment down if you need any indepth explanation of any of these\n
['Dynamic Programming']