leetcode

0 // Recursive, top down

1 class Solution {

2 typedef vector<int> Event;

3 vector<vector<int>> dp;

4

5 int rec(const vector<Event> &events, const vector<Event>::const_iterator it, int k) {

6 static const auto cmp = [](const Event &a, int val) { return a[0] <= val; };

7

8 if (!k || it == events.end()) return 0;

9 int idx = distance(events.begin(), it);

10 if (dp[k][idx] != -1) return dp[k][idx];

11

12 auto next = lower_bound(it, events.end(), (*it)[1], cmp);

13 int with = (*it)[2] + rec(events, next, k - 1);

14 int without = rec(events, it + 1, k);

15 return dp[k][idx] = max(with, without);

16 }

17

18 public:

19 int maxValue(vector<Event> &events, int k) {

20 static const auto cmp = [](const Event &a, const Event &b) { return a[0] < b[0]; };

21 sort(events.begin(), events.end(), cmp);

22

23 dp = vector(k + 1, vector(events.size(), -1));

24 return rec(events, events.begin(), k);

25 }

26 };

27

28 // Iterative, bottom up

29 class Solution {

30 typedef vector<int> Event;

31

32 public:

33 int maxValue(vector<Event> &events, int k) {

34 static const auto cmp = [](const Event &a, int val) { return a[0] <= val; };

35 static const auto cmp_sort = [](const Event &a, const Event &b) { return a[0] < b[0]; };

36 sort(events.begin(), events.end(), cmp_sort);

37

38 vector<vector<int>> dp(k + 1, vector(events.size() + 1, 0));

39

40 auto start = events.rbegin();

41 for (int i = events.size() - 1; i >= 0; i--, start++) {

42 auto it = lower_bound(start.base(), events.end(), events[i][1], cmp);

43 int offset = distance(events.begin(), it);

44 for (int cnt = 1; cnt <= k; cnt++) {

45 dp[cnt][i] = max(dp[cnt][i + 1], events[i][2] + dp[cnt - 1][offset]);

46 }

47 }

48

49 return dp[k][0];

50 }

51 };