You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The text was updated successfully, but these errors were encountered:
ramen-7
changed the title
Please cover this question in one of your videos:
Please cover this question in one of your videos https://leetcode.com/problems/maximize-the-profit-as-the-salesman/
Aug 20, 2023
Hi @ramen-7 ,
Actually this problem is only a Knapsack (take and skip) with a slight optimisation by applying binary search to find next house which can be bought after you buy current house.
See the code below :
`
class Solution {
public:
int N;
int t[100001];
int binary_search(int start, vector<vector<int>>& offers, int target) {
int l = start, r = offers.size()-1;
int result_idx = -1;
while(l <= r) {
int mid = l + (r-l)/2;
if(offers[mid][0] <= target) {
l = mid+1;
} else if(offers[mid][0] > target) {
result_idx = mid;
r = mid-1;
}
}
return result_idx;
}
int solve(int i, vector<vector<int>>& offers) {
if(i >= offers.size())
return 0;
if(t[i] != -1)
return t[i];
//ith customer
int house_end = offers[i][1];
int gold = offers[i][2];
int take = gold;
int next_house = binary_search(i+1, offers, house_end); //Find the next valid house you can buy
if(next_house != -1) {
take += solve(next_house, offers);
}
int skip = solve(i+1, offers);
return t[i] = max(take, skip);
}
int maximizeTheProfit(int n, vector<vector<int>>& offers) {
N = n;
memset(t, -1, sizeof(t));
sort(begin(offers), end(offers)); //Because if I take ith house, I need to find the next valid house I can buy (using binary search)
return solve(0, offers);
}
};
The recursive code I wrote obviously gave TLE but worked
The dp I tried to make from this did not work, if you could help me figure out why, I'll be grateful :)
The text was updated successfully, but these errors were encountered: