C++ | Recursion + DP | Workaround from TLE
TLE - 65/82 TC passed\nMy first try was pretty straight forward, include and don\'t include current ride\n\nclass Solution {\npublic:\n    long long helper(int 
1. TLE - 65/82 TC passed\nMy first try was pretty straight forward, include and don\'t include current ride\n```\nclass Solution {\npublic:\n    long long helper(int &n, vector<vector<int>>& rides,int i,int laststop,vector<long long> &dp)\n    {\n        if(i==rides.size()) return 0;\n        if(dp[laststop]!=-1) return dp[laststop];\n        long long ans=0;\n        int profit=rides[i][1]-rides[i][0]+rides[i][2];\n        ans=max(helper(n,rides,i+1,laststop,dp),rides[i][0]>=laststop?profit+helper(n,rides,i+1,rides[i][1],dp):0);\n        return dp[laststop]=ans;\n    }\n    \n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n    vector<long long> dp(n+1,-1);\n    sort(rides.begin(),rides.end());\n    return helper(n,rides,0,1,dp);\n    }\n};\n```\n\n2. TLE - 70/82 TC passed\nThen i want to start including the ride only if it\'s start point is greater than current stop.\nand changed my DP to calculate at a given position i rather than laststop.\n```\nclass Solution {\npublic:\n    long long helper(int &n, vector<vector<int>>& rides,int i,int laststop,vector<long long> &dp)\n    {\n        if(i==rides.size()) return 0;\n        if(dp[i]!=-1) return dp[i];\n        long long ans=0;\n        int profit=rides[i][1]-rides[i][0]+rides[i][2];\n        int j=i+1;\n        while(j<rides.size() && rides[j][0]<rides[i][1]) j++;\n        ans=max(helper(n,rides,i+1,laststop,dp),profit+helper(n,rides,j,rides[i][1],dp));\n        return dp[i]=ans;\n    }\n    \n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n    vector<long long> dp(rides.size(),-1);\n    sort(rides.begin(),rides.end());\n    return helper(n,rides,0,1,dp);\n    }\n};\n```\n\n3. Passing solution.\nCouldn\'t think to use binary search above because i thought since we already sorted and next valid ride will be close by. Thanks to intelligent people to discuss, i immediately corrected my mistake and it passed.\n```\nclass Solution {\npublic:\n    long long helper(int &n, vector<vector<int>>& rides,int i,int laststop,vector<long long> &dp)\n    {\n        if(i==rides.size()) return 0;\n        if(dp[i]!=-1) return dp[i];\n        long long ans=0;\n        int profit=rides[i][1]-rides[i][0]+rides[i][2];\n        int end=rides.size()-1,start=i+1,mid,next=end+1;\n        while(start<=end) \n        {\n            mid=start+(end-start)/2;\n            if(rides[mid][0]>=rides[i][1])\n            {\n                next=mid;\n                end=mid-1;\n            }\n            else start=mid+1;\n        }\n        ans=max(helper(n,rides,i+1,laststop,dp),profit+helper(n,rides,next,rides[i][1],dp));\n        return dp[i]=ans;\n    }\n    \n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n    vector<long long> dp(rides.size(),-1);\n    sort(rides.begin(),rides.end());\n    return helper(n,rides,0,1,dp);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C', 'Binary Tree', 'C++']