leetcode

0 class Solution {

1 public:

2 int jobScheduling(const vector<int> &startTime, const vector<int> &endTime,

3 const vector<int> &profit) const {

4 static int indices[50001];

5 const int n = profit.size();

6

7 iota(begin(indices), begin(indices) + n, 0);

8 sort(begin(indices), begin(indices) + n,

9 [&endTime](int a, int b) { return endTime[a] < endTime[b]; });

10

11 map<int, int> dp = {{0, 0}};

12 for (int i = 0; i < n; i++) {

13 const int idx = indices[i];

14 const int crnt = profit[idx] + prev(dp.upper_bound(startTime[idx]))->second;

15 if (crnt > dp.rbegin()->second) dp[endTime[idx]] = crnt;

16 }

17

18 return dp.rbegin()->second;

19 }

20 };