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 < mmeneg...@gmail.com> 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 <nishaant...@gmail.com> 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, adit.sh...@gmail.com < >> adit.sh...@gmail.com> 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: algogeeks@googlegroups.com >>> 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 < >>> prashant.r.k...@gmail.com> 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 < >>> rahulsinga...@gmail.com>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 algoge...@googlegroups.com. >>> >> To unsubscribe from this group, send email to >>> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com> >>> > >>> >> . >>> >> 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 algoge...@googlegroups.com. >>> > To unsubscribe from this group, send email to >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com> >>> > >>> > . >>> > 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
