C++ | DP | Resemblance to other LC question
This question is pretty much same as https://leetcode.com/problems/maximum-profit-in-job-scheduling/. Here is my code to that problem:\nTime complexity O(n^2)\n
This question is pretty much same as https://leetcode.com/problems/maximum-profit-in-job-scheduling/. Here is my code to that problem:\nTime complexity O(n^2)\n```\nclass Solution {\npublic:\n    vector<vector<int> > job;\n    map<int,int> dp;\n    int n;\n    \n    int solve(int pos){\n        if(pos>=n) return 0;\n\t\t\n        if(dp.find(pos)!=dp.end()) return dp[pos];\n        \n        int next;\n        for(next=pos+1;next<n;next++){\n            if(job[next][0]>=job[pos][1]) break;\n        }\n    \n        return dp[pos]= max(solve(pos+1), solve(next)+job[pos][2]);\n    }\n    \n    int jobScheduling(vector<int>& start, vector<int>& end, vector<int>& profit) {\n        n=profit.size();\n        for(int i=0;i<n;i++){\n            job.push_back({start[i], end[i], profit[i]});\n        }\n        sort(job.begin(), job.end());\n        \n        return solve(0);\n    }\n};\n```\n\nNow lets come to this question. Firstly you can simply update the profit/tip to be (end-start+profit/tip). Here\'s my working code to this problem:\nHad to use binary search in this one, because the O(n^2) solution was giving TLE.\n```\nclass Solution {\npublic:\n    vector<vector<int> > job;\n    map<int,long long int> dp;\n    int m;\n    \n    long long int solve(int pos){\n        if(pos>=m) return 0;\n        \n        if(dp.find(pos)!=dp.end()) return dp[pos];\n        \n        \n        int hi=m-1;\n        int lo=pos+1;\n        int next=hi+1;\n        \n        while(lo<=hi){\n            int mid= lo+(hi-lo)/2;\n            if(job[mid][0]>=job[pos][1]){\n                next=mid;\n                hi=mid-1;\n            }\n            else lo=mid+1;\n        }\n        \n        // for(i=pos+1;i<m;i++){\n        //     if(job[i][0]>=job[pos][1]) break;\n        // }\n        return dp[pos]= max(solve(pos+1), solve(next)+job[pos][2]);\n    }\n\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        for(auto& it: rides){\n            it[2]+=(it[1]-it[0]);\n        }\n        m=rides.size();\n        sort(rides.begin(), rides.end());\n        this->job = rides;\n        return solve(0);\n    }\n};\n```\nSee, same questions, just a bit change in language. \nKindly upvote!
['Dynamic Programming', 'C', 'Binary Tree']