lintcode题目记录4

<span style="color: #0000ff">class</span><span style="color: #000000"> Solution:    </span><span style="color: #008000">#</span><span style="color: #008000"> @param {int[][]} envelopes a number of envelopes with widths and heights</span>    <span style="color: #008000">#</span><span style="color: #008000"> @return {int} the maximum number of envelopes</span>    <span style="color: #0000ff">def</span><span style="color: #000000"> maxEnvelopes(self, envelopes):        </span><span style="color: #008000">#</span><span style="color: #008000"> Write your code here</span>        <span style="color: #0000ff">import</span><span style="color: #000000"> functools        nums </span>= sorted(envelopes,key= functools.cmp_to_key(<span style="color: #0000ff">lambda</span> x,y:x[0]-y[0] <span style="color: #0000ff">if</span> x[0] != y[0] <span style="color: #0000ff">else</span> y[1] - x[1<span style="color: #000000">]))        size </span>=<span style="color: #000000"> len(nums)        dp </span>=<span style="color: #000000"> []        </span><span style="color: #0000ff">for</span> x <span style="color: #0000ff">in</span><span style="color: #000000"> range(size):            low, high </span>= 0, len(dp) - 1            <span style="color: #0000ff">while</span> low <=<span style="color: #000000"> high:                mid </span>= (low + high)//2                <span style="color: #0000ff">if</span> dp[mid][1] < nums[x][1<span style="color: #000000">]:                    low </span>= mid + 1                <span style="color: #0000ff">else</span><span style="color: #000000">:                    high </span>= mid - 1            <span style="color: #0000ff">if</span> low <<span style="color: #000000"> len(dp):                dp[low] </span>=<span style="color: #000000"> nums[x]            </span><span style="color: #0000ff">else</span><span style="color: #000000">:                dp.append(nums[x])        </span><span style="color: #0000ff">return</span> len(dp)