Thanx for the reply but I didnt get you. What does dp[i] represent ? On Thu, Jan 24, 2013 at 9:50 PM, sunny <[email protected]> wrote:
> take a structure or pair of start time and finish time and then sort the > the structure you know the comparator function the for each for each dp[i] > select j belongs to (0,i) and then count the overlap value > > > if(j==0) > dp[i]=max(dp[i],match); > else > dp[i]=max(dp[i],dp[j-1]+match); > > > with this recursive relation my code got accepted in .24 sec others > approach you mentioned may lead to the TLE > > On Thursday, January 24, 2013 1:35:38 PM UTC+5:30, emmy wrote: >> >> please help me with the following problem: >> http://www.spoj.com/problems/**JUICE/<http://www.spoj.com/problems/JUICE/> >> >> bit mask will require very large memory. >> If I sort the intervals in decreasing order of their start time.. I still >> cant make it to a dp >> If I sort the intervals in decreasing order of their finish times I am >> still not getting a recurrence for dp that is valid >> If I convert this to an interval graph, I have to find the maximum number >> of vertices that can be included in some clique of size >=3. But this also >> seems like a brute force approach. >> >> Which approach to try?? please help!! >> >> -- > > > --
