C++ || Brute ( Recursion ) -> Better ( DP ) -> Optimal ( DP + Binary Search ) || Clear and Concise
1. Brute Force ( Recursion )\n In brute force we use simple recursion technique and opt between two choices:\n1. Opt for an ride and add value to the answer\n2.
## 1. Brute Force ( Recursion )\n In brute force we use simple recursion technique and opt between two choices:\n1. Opt for an ride and add value to the answer\n2. Skip the ride and move ahead\n\n```\nclass Solution {\npublic:\n    long long recur(vector<vector<int>>&rides,int nn,int idx)\n    {\n        if(idx>=nn)\n            return 0;\n        int i;\n        for(i=idx+1;i<nn;i++)\n        {\n            if(rides[i][0]>=rides[idx][1])\n                break;\n        }\n        long long op1=recur(rides,nn,idx+1);\n        long long op2=rides[idx][1]-rides[idx][0]+rides[idx][2]+recur(rides,nn,i);\n        \n        return max(op1,op2);\n    }\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        \n        sort(rides.begin(),rides.end());\n        int nn=rides.size();\n        \n        return recur(rides,nn,0);\n    }\n};\n```\n\n## 2. Better Approach ( Recursion + Memoization )\n\n```\nclass Solution {\npublic:\n    long long dp[(int)1e5];\n    long long recur(vector<vector<int>>&rides,int nn,int idx)\n    {\n        if(idx>=nn)\n            return 0;\n        int i;\n        if(dp[idx]!=-1)\n            return dp[idx];\n        for(i=idx+1;i<nn;i++)\n        {\n            if(rides[i][0]>=rides[idx][1])\n                break;\n        }\n        long long op1=recur(rides,nn,idx+1);\n        long long op2=rides[idx][1]-rides[idx][0]+rides[idx][2]+recur(rides,nn,i);\n        \n        return dp[idx]=max(op1,op2);\n    }\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        \n        sort(rides.begin(),rides.end());\n        int nn=rides.size();\n        memset(dp,-1,sizeof dp);\n        return recur(rides,nn,0);\n    }\n};\n```\n\n## 3. Optimal Approach ( Recursion + Memoization + Binary Search )\n\n```\nclass Solution {\npublic:\n    long long dp[(int)1e5];\n   int find(vector<vector<int>>&events,int start,int toFind)\n    {\n        int low=start;\n        int high=events.size()-1;\n        int ans=-1;\n        while(low<=high)\n        {\n            int mid=(low+high)/2;\n            \n            if(events[mid][0]>=toFind)\n            {\n                ans=mid;\n              high=mid-1;\n            }\n            else\n            {\n                low=mid+1;\n            }\n        }\n      \n        return ans;\n        \n    }\n    long long recur(vector<vector<int>>&rides,int nn,int idx)\n    {\n        if(idx>=nn)\n            return 0;\n       if(idx<0)\n           return 0;\n        if(dp[idx]!=-1)\n            return dp[idx];\n        \n        /* O(n) time in worst case */\n        // for(i=idx+1;i<nn;i++)\n        // {\n        //     if(rides[i][0]>=rides[idx][1])\n        //         break;\n        // }\n        \n        /* O(logn) time in worst case Binary Search */\n        int i=find(rides,idx+1,rides[idx][1]);\n        long long op1=recur(rides,nn,idx+1);\n        long long op2=rides[idx][1]-rides[idx][0]+rides[idx][2]+recur(rides,nn,i);\n        \n        return dp[idx]=max(op1,op2);\n    }\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        \n        sort(rides.begin(),rides.end());\n        int nn=rides.size();\n        memset(dp,-1,sizeof dp);\n        return recur(rides,nn,0);\n    }\n};\n```\n\n\n**Pls upvote if you found the post to be helpful.**\n\n
['Dynamic Programming', 'Recursion', 'C', 'Binary Tree', 'C++']