题解 | 信封嵌套

def maxEnvelopes(envelopes):
    if not envelopes:
        return 0

    # 按照长度升序排列，如果长度相同则按照宽度降序排列
    envelopes.sort(key=lambda x: (x[0], -x[1]))

    # 提取宽度并寻找最长递增子序列
    widths = [envelope[1] for envelope in envelopes]
    dp = []

    for width in widths:
        # 使用二分查找找到第一个大于等于当前宽度的位置
        left, right = 0, len(dp)
        while left < right:
            mid = (left + right) // 2
            if dp[mid] >= width:
                right = mid
            else:
                left = mid + 1
        # 如果找到的位置等于 dp 的长度，说明当前宽度比所有元素都大，直接添加到末尾
        if left == len(dp):
            dp.append(width)
        else:
            # 否则替换掉第一个大于等于当前宽度的元素
            dp[left] = width

    return len(dp)


# 输入处理
n = int(input())
envelopes = []
for _ in range(n):
    l, w = map(int, input().split())
    envelopes.append((l, w))
# 输出结果
print(maxEnvelopes(envelopes))