sub-optimal but simple N^2 python solution, with pruning, accepted


  • 0
    E

    Sort the envelopes by either area or sum of dimensions, as long as the ith envelope can only contain those with index ii<i.

    For each envelope i, compute mx[i], the maximum number of envelopes that can i can "russian-doll", including itself. For the smallest envelope, mx[0]=1. For i>0, take the russian-doll max of any envelope ii: ii<i to its left as long i can "russian-doll" ii.

    To help with pruning, record also the maximum seen so far: gmx[ii] after using the first ii envelopes. If at any time, we are at candidate ii and we can already russian-doll at least gmx[ii] envelopes, we know we can stop, since any candidate further on the left will not yield a larger value.

    class Solution(object):
        def maxEnvelopes(self, envs):
            """
            :type envelopes: List[List[int]]
            :rtype: int
            """
            areas=[(w*h, (w,h)) for (w,h) in envs]
            areas.sort()
    
            mx=[]
            gmxs=[]
            gmx=0
    
            for (i,(a,env)) in enumerate(areas):
                w,h=env
                cnt=0
                for ii in xrange(i-1,-1,-1):
                    aa, env2=areas[ii]
                    (w2,h2)=env2
                    if w>w2 and h>h2 and mx[ii]>cnt:
                        cnt=mx[ii]
                    if gmxs[ii]<=cnt:
                        break
                cnt+=1
                mx.append(cnt)
                gmx=max(cnt,gmx)
                gmxs.append(gmx)
    
            return gmx
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.