Maximum Earnings From Taxi LeetCode solution in C++

1
class Solution {
2
  long long dp[100005];
3
  // Searching for next passenger who can sit in the car
4
  int binarySearch(vector<vector<int>> &rides, int val) {
5
    int s = 0, e = rides.size() - 1;
6
    int ans = rides.size();
7
    while (s <= e) {
8
      int mid = s + (e - s) / 2;
9
      if (rides[mid][0] >= val) {
10
        ans = mid;
11
        e = mid - 1;
12
      } else {
13
        s = mid + 1;
14
      }
15
    }
16
    return ans;
17
  }
18

19
  long long helper(int i, vector<vector<int>> &rides) {
20
    if (i == rides.size()) {
21
      return 0;
22
    }
23
    if (dp[i] != -1) return dp[i];
24
    long long op1 = helper(i + 1, rides); // We didn't pick this ith passenger
25
    int idx = binarySearch(rides, rides[i][1]);
26
    long long op2 =
27
        rides[i][1] - rides[i][0] + rides[i][2] + helper(idx, rides); // We pick this ith passenger
28
    return dp[i] = max(op1, op2);
29
  }
30

31
 public:
32
  long long maxTaxiEarnings(int n, vector<vector<int>> &rides) {
33
    memset(dp, -1, sizeof dp);
34
    sort(rides.begin(), rides.end());
35
    return helper(0, rides);
36
  }
37
};