weighted Job Scheduling , C++
\n\nWe have two choice\n\nTake this job with the last non overlapping job\nDon\'t take this job\nSo, for the first option we have to compute which job is not ov
\n\nWe have two choice\n\nTake this job with the last non overlapping job\nDon\'t take this job\nSo, for the first option we have to compute which job is not overlapping to this job. It takes O(N) to compute for each job.\nAnd for the second option we just take its previous profit without including current job.\n```\n#define ll long long \nclass Solution {\npublic:\n    long long maxTaxiEarnings(int n, vector<vector<int>>& jobs) \n    {\n        for(auto &x:jobs) x[2] += x[1]-x[0];\n        \n        map<ll,ll> dp;\n        \n        sort(jobs.begin(), jobs.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[0] > b[0];\n        });\n        ll maxT = 0;\n        for (auto job : jobs) {\n            auto it = dp.lower_bound(job[1]);\n            ll pre = (it == dp.end()) ? 0 : it->second;\n            maxT = max(maxT, job[2] + pre);\n            dp[job[0]] = maxT;\n        }\n        \n        return maxT;\n        \n    }\n};\n```
[]