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/
>
> 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!!
>
>
--
