Java Solution with Recursion Memoization and binary search
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is to find which points to take and which points to discard.\nIf first poin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is to find which points to take and which points to discard.\nIf first point is taken the next point can only be selected when the trip of first point got completed i.e the end point of first trip is less than or equal to start point of next trip\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe problem is similar to knapsack problem where we have to select and discard the points.\nFirst we sort all the trip with starting points so than we can compute \nchronologically\nAfter that we will iterate throgh the points selecting and rejecting based on out criteria. In order to search the next point we can use binary search\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n\n    long  dp[];\n\n    Solution(){\n        dp=new long[100001];\n\n        Arrays.fill(dp,-1);\n    }\n\n    int findNextStartTime(int rides[][], int start,int target){\n        int beg = start;\n        int end=rides.length-1;\n        int res=-1;\n\n        while(beg<=end){\n            int mid = (beg + end)/2;\n\n            if(rides[mid][0] >= target){\n                res = mid;\n                end=mid-1;\n            }else{\n                beg=mid+1;\n            }\n        }\n\n        return res;\n    }\n\n    \n    public long maxTaxiEarnings(int n, int[][] rides) {\n        int ridesLen = rides.length;\n        int idx=0;\n\n        Arrays.sort(rides,new Comparator<int[]>(){\n            public int compare(int x[], int y[]){\n                return Integer.compare(x[0],y[0]);\n            }\n        });\n\n       long ans = solve(rides,ridesLen,idx);\n\n       return ans;\n    }\n\n    long solve(int rides[][], int ridesLen, int idx){\n\n        if(idx >= ridesLen){\n            return 0;\n        }\n\n        if(idx < 0){\n            return 0;\n        }\n\n        if(dp[idx] != -1){\n            return dp[idx];\n        }\n\n        //need to select the next point which chan be picked\n        int i=0;\n        \n        // for(i=idx+1;i<ridesLen;i++){\n        //     //the point can be picked when the first trip ends\n        //     //i.e if endTime of first trip is less than or equal start time of\n        //     //next trip\n\n        //     if(rides[idx][1] <= rides[i][0]){\n        //         break;\n        //     }\n            \n        // }\n\n        i=findNextStartTime(rides,idx+1,rides[idx][1]);\n\n        long pick = rides[idx][1] - rides[idx][0]+rides[idx][2] + solve(rides,ridesLen,i);\n        long notPick =solve(rides,ridesLen,idx+1);\n\n        return dp[idx] = Math.max(pick,notPick);\n    }\n}\n```
['Binary Search', 'Recursion', 'Memoization', 'Java']