Maximum Number of Events That Can Be Attended II LeetCode solution in C++

1
class Solution {
2
 public:
3
  int ans;
4
  unordered_map<int, unordered_map<int, unordered_map<int, int>>> dp;
5

6
  int Solve(vector<vector<int>> &events, int start, int n, int k, int endtime) {
7
    if (k == 0 || start == n) {
8
      return 0;
9
    }
10

11
    if (dp.find(start) != dp.end() && dp[start].find(k) != dp[start].end() &&
12
        dp[start][k].find(endtime) != dp[start][k].end()) {
13
      return dp[start][k][endtime];
14
    }
15
    int t1 = 0;
16
    if (events[start][0] > endtime) {
17
      t1 = events[start][2] + Solve(events, start + 1, n, k - 1, events[start][1]);
18
    }
19

20
    int t2 = Solve(events, start + 1, n, k, endtime);
21

22
    dp[start][k][endtime] = max(t1, t2);
23
    // cout<< dp[start][k][endtime]<<endl;
24

25
    return dp[start][k][endtime];
26
  }
27
  int maxValue(vector<vector<int>> &events, int k) {
28
    dp.clear();
29

30
    // sort according to start time
31
    sort(events.begin(), events.end(), [](vector<int> &a, vector<int> &b) { return a[0] < b[0]; });
32

33
    return Solve(events, 0, events.size(), k, 0);
34
  }
35
};