C++ | DP | Concise|similar to Job Scheduling
This question is same as Maximum Profit in Job Scheduling this question\n\n1. Start from the last passenger(having largest start(i)) and move backwards. (used p
This question is same as [Maximum Profit in Job Scheduling](https://leetcode.com/problems/maximum-profit-in-job-scheduling/) this question\n```\n1. Start from the last passenger(having largest start(i)) and move backwards. (used priority_queue)\n2. As we move backwards for each start(i) store the maximum amount that\n   we can get from from that position onwards.\n 3.Maximum amount at any start(i)=amount of current ride +max. amount after current rides completes(lower_bound of end(i) of current ride. \n```\nTime complexity:- O(nlog(n))\nSpace complexity:- O(n)\n```\nclass Solution {\npublic:\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n      priority_queue<vector<int>>pq;\n        for(auto & i:rides)\n            pq.push(i);\n        long long ans=0;\n        map<int,long long>mp;\n        while(!pq.empty())\n        {\n            auto vec=pq.top();\n            pq.pop();\n            long long p=vec[1]-vec[0]+vec[2];\n            auto it=mp.lower_bound(vec[1]);\n            if(it!=mp.end())\n             p+=it->second;\n            mp[vec[0]]=max(ans,p);\n            ans=max(ans,p);\n        }\n        return ans;\n    }\n};\n```\nDo **UPVOTE** if it helps :)\nIf you have any doubt then please ask in comment section.
['Dynamic Programming', 'C']