Can anybody give the approach to solve this problem CHEFSTCK of sept loc.
I know my english is bad and sorry for that and also i am writing this for the first time, so, if anything is unclear feel free to ask !
see at first think of brute force approach : at every pair we have two possibilities i.e either take this one or completely reject this in our solution set.
The above approach clearly lead to an O(2^N) solution …much slow (:
Now, lets think something , at every pair we can reject some of the pairs (those which overlap on the current pair partially or completely) and start our calculation after that pair (remember this is only possible if you have already sorted the initial given pairs). Now, this also in worst case leads to an O(2^N) solution .
But, one thing to note here is that after including certain pair and then calculating our answer about that…the answer will be same all the time whenever we are asked to find the best possible answer about a particular pair (i.e. after that pair)
So, this will give us the way to use DP and store the answers and thus out O(2^N) solution will reduce to O(N^2).
example : suppose our pairs are
1 5
5 7
5 10
5 8
6 12
Now, at first we sort it :
1 5
5 7
5 8
5 10
6 12
Now, let’s suppose that first pair (i.e (1, 5) ) is in our solution set and so, we have curr_ans = 1 (as it starts with 1)
so, we directly jump to the pair whose start is equal to (preferably) or just greater than…here we are unlucky so w land on the very next pair (5, 7)
Now, to take this or not is not our concern we can simply take this and find the best way (best way after this index with taking this index into our solution)
How, the answer will not change ?
suppose we are at a position and we want to find the best possible after this (note that it is independent of the fact that what was the previous pair that we include in our solution set… HOW?? we are including a pair and then we are just wondering about what was the best possible solution with it’s right_end as we are already take cares of the fact that what was the answer below left_end and we want only best possible about right_end after curr_index. (again don’t confuse that the decision that whether to take this pair or not still remains AS we have taken this pair and then want the best after it ! ) )
so, we can take an array DP[100001] and then store answer during recursion and at each step we are considering all the indices after the current one…so, for each we have to find the value of at least N recur(val) (worst case) and since because of Dp array each indices is calculated just once . so, the total complexity is O(N^2) !
IMPLEMENTATION : https://ideone.com/avg4zX
But, unfortunately this even don’t pass (:
Now, the one with O(N logN)
You made 2 answers of that one? :o
i don’t know how but yesterday when i answered this , the entire answer was not posted . so, when i see this today, i post the rest!
@vijju123 even now i don’t know how it’s showing incomplete answer (although after posting it i have checked !)