This problem is a variation of Longest Increasing Subsequence (LIS). The faster algorithm é O(n log n)
http://en.wikipedia.org/wiki/Longest_increasing_subsequence http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence Wladimir Araujo Tavares http://www.si.ufc.br/~wladimir <http://www.si.ufc.br/%7Ewladimir/> "Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos." On Mon, Oct 18, 2010 at 7:53 PM, Marcelo Amorim Menegali < [email protected]> wrote: > The problem statement doesn't make it clear, but I guess one can rotate the > envelopes (i.e. exchange x_i and y_i). > I mean, in the example case of {(1,2),(2,13),(5,10),(7,9),(9,1)}, isn't > (1,2),(1,9),(5,10) a valid solution (with length 3), instead of the ones > shown (with length 2)? > > > On Sat, Oct 16, 2010 at 5:40 PM, nishaanth <[email protected]> wrote: > >> ya...finding the longest subsequence is the simplest method...and its >> nlogn.. >> >> It works...it similar to box stacking problem >> >> >> On Fri, Oct 1, 2010 at 6:00 AM, [email protected] < >> [email protected]> wrote: >> >>> The problem here is more about finding the most optimal solution and not >>> just solution. >>> Rgds >>> Adi >>> -----Original Message----- >>> From: Sathaiah Dontula >>> Sent: 29/09/2010, 09:25 >>> To: [email protected] >>> Subject: Re: [algogeeks] Algorithm to determine the largest number of >>> envelopes that can be nested inside one another. >>> >>> >>> I think we can do like this, >>> >>> 1. Sort all the xi's in ascending order -> nlog(n) >>> 2. Then find the longest increasing sequence of yi's -> nlog(n) >>> 3. complexity will be nlog(n). >>> >>> Thanks, >>> Sathaiah Dontula >>> >>> On Tue, Sep 28, 2010 at 11:37 PM, Prashant Kulkarni < >>> [email protected]> wrote: >>> >>> > i think it is similar to finding max in a list O(n) or sorting >>> algorithm >>> > O(n log n) >>> > >>> > -- Prashant Kulkarni >>> > >>> > >>> > >>> > >>> > On Tue, Sep 28, 2010 at 11:33 PM, Rahul Singal < >>> [email protected]>wrote: >>> > >>> >> A possible solution i can think is create a directed graph where each >>> >> vertex is a envelope and edges are from a bigger envelope to smaller >>> >> envelope ( one which can fit in bigger envelope ) . Now the problem is >>> >> reduce to finding longest path in the graph . >>> >> >>> >> Regards >>> >> Rahul >>> >> >>> >> -- >>> >> You received this message because you are subscribed to the Google >>> Groups >>> >> "Algorithm Geeks" group. >>> >> To post to this group, send email to [email protected]. >>> >> To unsubscribe from this group, send email to >>> >> [email protected]<algogeeks%[email protected]> >>> <algogeeks%[email protected]<algogeeks%[email protected]> >>> > >>> >> . >>> >> For more options, visit this group at >>> >> http://groups.google.com/group/algogeeks?hl=en. >>> >> >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups >>> > "Algorithm Geeks" group. >>> > To post to this group, send email to [email protected]. >>> > To unsubscribe from this group, send email to >>> > [email protected]<algogeeks%[email protected]> >>> <algogeeks%[email protected]<algogeeks%[email protected]> >>> > >>> > . >>> > For more options, visit this group at >>> > http://groups.google.com/group/algogeeks?hl=en. >>> > >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> S.Nishaanth, >> Computer Science and engineering, >> IIT Madras. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
