✅C++ || Explained || Recursion->Memoization->Binary Search
Intuition:\n\nour idea behind solving this problem is simple\n* we will sort all rides according to passenger arriving time\n* now we keep checking all possible
Intuition:\n\nour idea behind solving this problem is simple`\n* we will sort all rides according to passenger arriving time\n* now we keep checking all possible earnings by: if the passenger picked up or if he\'s not.\n* we can only pick the passenger if the ride end time of our current passenger is more than or equal to arrival time of next passenger( as two passenger can\'t be given ride together), this is what we check inside our for loop.\n* Case 1: if we pick the passenger then we can only pick next passenger after this ride end so update the index till next possible time\n* Case 2: if we does\'nt pick the passenger we can simply move on to next passenger so increase index by 1.\n\n\n\n**Recursion (TLE):**\n\n```\nclass Solution {\npublic:\n    long long solve(int index,int n,vector<vector<int>>& rides)\n    {\n        if(index>=rides.size())return 0;\n      \n        int i=0;\n       for(i=index+1;i<rides.size();i++)\n       {\n           if(rides[i][0]>=rides[index][1])break;\n       }\n        int pick=rides[index][1]-rides[index][0]+rides[index][2]+solve(i,n,rides);\n        int notpick=solve(index+1,n,rides);\n        return max(pick,notpick);\n    }\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        sort(rides.begin(),rides.end());\n        return solve(0,n,rides);\n    }\n};\n```\n\n**Recursion with Memoization:( TLE again on large test cases)**\n```\nclass Solution {\npublic:\n    long long solve(int index,int n,vector<vector<int>>& rides,vector<long long> &dp)\n    {\n        if(index>=rides.size())return 0;\n        if(dp[index]!=-1)return dp[index];\n        int i=0;\n       for(i=index+1;i<rides.size();i++)\n       {\n           if(rides[i][0]>=rides[index][1])break;\n       }\n        long long pick=rides[index][1]-rides[index][0]+rides[index][2]+solve(i,n,rides,dp);\n        long long notpick=solve(index+1,n,rides,dp);\n        return dp[index]=max(pick,notpick);\n    }\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<long long> dp(rides.size()+1,-1);\n        sort(rides.begin(),rides.end());\n        return solve(0,n,rides,dp);\n    }\n};\n```\n\u2705\u2705**Recursion Memoization with Binary search:**\n`in this approach in order to find our next possible passenger we use binary search`\n\n```\nclass Solution {\npublic:\n    long long solve(int index,int n,vector<vector<int>>& rides,vector<long long> &dp)\n    {\n        if(index>=rides.size())return 0;\n        if(dp[index]!=-1)return dp[index];\n        int i=rides.size();\n        int low=index+1,high=rides.size()-1;\n        while(low<=high)\n        {\n            int mid=(low+high)/2;\n            if(rides[mid][0]>=rides[index][1])\n            {\n                i=mid;\n                high=mid-1;\n            }\n            else\n                low=mid+1;\n        }\n        long long pick=rides[index][1]-rides[index][0]+rides[index][2]+solve(i,n,rides,dp);\n        long long notpick=solve(index+1,n,rides,dp);\n        return dp[index]=max(pick,notpick);\n    }\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<long long> dp(rides.size()+1,-1);\n        sort(rides.begin(),rides.end());\n        return solve(0,n,rides,dp);\n    }\n};\n```
['Binary Search', 'Recursion', 'Memoization']