c++ | memoization + binary search
Idea\nFor every ar[i], I have 2 options: attend or not attend.\nIn case I don\'t attend, simply proceed forward by doing pos+1.\nIn case we attend a particular 
<b>Idea</b>\nFor every `ar[i]`, I have 2 options: attend or not attend.\nIn case I don\'t attend, simply proceed forward by doing `pos+1`.\nIn case we attend a particular trip, find the next index from which, we can attend trips without intersecting with the current trip. If we do this search linearly, our time complexity will reach O(`n^2`). So, we sort the array beforehand with respect to the start of the trip and using binary search, find the next index. This brings the time complexity to O(`n*logn`). Finally, we memoize our results to save repeated calculations.\nPlease comment if anything is unclear.\n```\nlong long dp[30001];\nclass Solution {\npublic:\nlong long help(vector<vector<int>> &ar,int pos){\n    int n=ar.size();\n    if(pos==n) return 0;\n    if(dp[pos]!=-1) return dp[pos];\n    // either I attend ar[pos] trip or not\n    long long ans=help(ar,pos+1);\n    // find the first starting time JUST greater than ending time of ar[pos] in log(n) time using binary search\n    int lo=pos+1,hi=n-1,nextPos=n;\n    while (lo<=hi){\n        int mid=lo+(hi-lo)/2;\n        if(ar[mid][0]>=ar[pos][1]){\n            nextPos=mid;\n            hi=mid-1;\n        }else lo=mid+1;\n    }\n    dp[pos]=max(ans,ar[pos][2]+help(ar,nextPos));\n    return dp[pos];\n}\n\nlong long maxTaxiEarnings(int n, vector<vector<int>>& ar) {\n    memset(dp,-1,sizeof(dp));\n    for(auto &it:ar) it[2]+=it[1]-it[0];\n    sort(ar.begin(),ar.end());\n    return help(ar,0);\n}\n};\n```
['Memoization', 'Binary Tree']