题解 | #信封嵌套问题#

信封嵌套问题

http://www.nowcoder.com/practice/9b9fe43a92b74408988e20331b10f6b4

n = int(input())
envlope = []
for _ in range(n):
    envlope.append(list(map(int, input().split())))
envlope.sort(key = lambda x: (x[0], -x[1]))
res = 0
ends = [0] * n
for _, length in envlope:
    l, r = 0, res
    while l < r:
        m = (l + r) // 2
        if ends[m] < length:
            l = m + 1
        else:
            r = m
    ends[r] = length
    if r == res:
        res += 1
print(res)
    
全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务