### Black_hat123's blog

By Black_hat123, history, 11 months ago, , Hello, can any one please tell how to solve This question Comments (4)
 » Firstly, sort the indices in chronological order. Secondly, we can define dp[i] as the maximum amount of money we can obtain at time a[i]. We can then say that this amount can be represented as the best out of these 2 values: We don't use interval i: the maximum amount of money we can obtain from a[i+1]...N We do use interval i: Define j as the first interval such that s[j] > e[i] (in other words, the first disjoint interval after i). Then, the value would be (the maximum possible money obtained from j..N) + p[i]. In terms of reccurence relation, this would be: dp[i] = max(dp[i+1], dp[j]+p[i])This gives us an O(N^2) solution, which will definetly TLE. However, we notice that for all intervals i+1..N, there is always an interval j such that intervals i and j are disjoint, and that for all k from i+1..j-1, k and i are not disjoint. Therefore, we can binary search to find the value j. The total complexity therefore becomes O(NlgN)My codeHope this helped!
•  » » Thanks man, that is really helpful.
 » Code#include #include #include #include #define ff first #define ss second #define ll long long using namespace std; const int N = 400 * 1000 + 5; pair> p[N]; vector > v[N]; int main() { int n; cin >> n; map m; for (int i = 0; i < n; i++) { int a, b, pi; cin >> a >> b >> pi; p[i] = {a, {b, pi}}; m[a], m[b]; } // map your starting and ending times to smaller values int x = 0; for (auto g : m) { m[g.first] = ++x; } // v[i] contains all the intervals whose start point is i for (int i = 0; i < n; i++) { v[m[p[i].ff]].emplace_back(m[p[i].ss.ff], p[i].ss.ss); } // for every interval starting at i you update it's answer vector dp(N); for (int i = 1; i < N; i++) { for (auto g : v[i]) dp[g.ff] = max(dp[g.ff], dp[i - 1] + g.ss); dp[i] = max(dp[i], dp[i - 1]); } cout << dp[N - 1]; } Please feel free to ask if anything is ambiguous.
•  » » Got it, Thank you