搭积木
搭积木
https://www.nowcoder.com/questionTerminal/55371b74b2f243e3820e57ee4c7b5504
题目描述：
链接：https://www.nowcoder.com/questionTerminal/55371b74b2f243e3820e57ee4c7b5504
来源：牛客网
来源：牛客网
小明有一袋子长方形的积木，如果一个积木A的长和宽都不大于另外一个积木B的长和宽，则积木A可以搭在积木B的上面。好奇的小明特别想知道这一袋子积木最多可以搭多少层，你能帮他想想办法吗？
定义每一个长方形的长L和宽W都为正整数，并且1 <= W <= L <= INT_MAX, 袋子里面长方形的个数为N, 并且 1 <= N <= 1000000.
假如袋子里共有5个积木分别为 (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), 则不难判断这些积木最多可以搭成4层, 因为(2, 2) < (2, 4) < (2, 5) < (4, 5)。
输入描述:
第一行为积木的总个数 N 之后一共有N行，分别对应于每一个积木的宽W和长L
输出描述:
输出总共可以搭的层数
示例1
输入
5 2 2 2 4 3 3 2 5 4 5
输出
4
知识点：
1、bisect
2、
W, L = map(int, input().split())
arr.append((W, L))
arr.append((W, L))
与
arr.append(list(map(int, input().split())))
的空间复杂度是不一样的
完整代码：
from bisect import bisect n = int(input()) arr = [] for _ in range(n): W, L = map(int, input().split()) arr.append((W, L)) arr.sort() result = [] for ele in arr: if not result: result.append(ele[1]) elif result[-1] <= ele[1]: result.append(ele[1]) else: index = bisect(result, ele[1]) result[index] = ele[1] print(len(result))
大疆公司氛围 168人发布
