Sort the envelopes first by increasing width. For each block of same-width envelopes, sort by decreasing height.
Then find the longest increasing subsequence of heights.
Since each same-width subarray is non-increasing in height, we can never pick more than one height within each width (otherwise heights would be non-increasing)
Thus, the resulting longest increasing heights subsequence is also increasing in width.
sort by increasing widths, then decreasing heights:
Get the heights:
Find the length longest increasing subsequence:
(Note that we could not have picked more than one evelope with width 6)
class Solution(object): def maxEnvelopes(self, envs): """ :type envelopes: List[List[int]] :rtype: int """ # sort first by increasing width # within each subarray of same-width envelopes # sort by decreasing height envs.sort(key=lambda (w,h): (w,-h)) # now find the length of the longest increasing subsequence of heights. # Since each same-width block was sorted non-increasing, # we can only pick at most one height within each block # otherwise, the sequence would be non-increasing tails= for (w,h) in envs: idx=bisect.bisect_left(tails, h) if idx==len(tails): tails.append(h) elif idx==0 or tails[idx-1]<h: tails[idx]=h return len(tails)