Black_hat123's blog

By Black_hat123, history, 5 years ago, In English

Hello, can any one please tell how to solve This question

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

  1. We don't use interval i: the maximum amount of money we can obtain from a[i+1]...N

  2. 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 code

Hope this helped!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Code

Please feel free to ask if anything is ambiguous.