Untitled

unknown
plain_text
20 days ago
1.9 kB
0
Indexable
Never
```class Solution {
public:

long long dp[100001];
static bool compare(vector<int> &a, vector<int> &b) {
if(a[0]<b[0]) {
return true;
} else if (a[0]> b[0]) {
return false;
} else {
if(a[1]<b[1]) {
return true;
} else if(a[1]>b[1]) {
return false;
} else {
return a[2]<b[2];
}
}

}

int find(int dest, int n , vector<vector<int>> &rides) {
int low = 0;
int high = n-1;
int ans = -1;
while(low<=high) {
int mid = low + (high-low)/2;

if(rides[mid][0]>=dest) {
ans = mid;
high = mid-1;
} else {
low = mid+1;
}
}

return ans;
}

long long recur(int index, int n, vector<vector<int>>& rides) {
if(index==n)
return 0;
if(index==-1)
return 0;
if(dp[index]!=-1)
return dp[index];

int dest = find(rides[index][1], n, rides);
//cout<<"dest:"<< dest<<endl;
long long skipCur = recur(index+1, n, rides);
long long withCur = rides[index][1]-rides[index][0]+rides[index][2] + recur(dest, n, rides);

dp[index]= max(skipCur, withCur);
return dp[index];

}

long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
sort(rides.begin(), rides.end());
memset(dp, -1, sizeof(dp));
// for(auto it: rides) {
//     cout<<it[0]<<" "<<it[1]<<" "<<it[2]<<endl;
// }

return recur(0, rides.size(), rides);

return 0;
}
};```