首页 > 试题广场 >

子集

[编程题]子集

小强现在有 $n$ 个物品,每个物品有两种属性 $x_i$ 和 $y_i$ .他想要从中挑出尽可能多的物品满足以下条件:对于任意两个物品 $i$ 和 $j$ ,满足 $x_i < x_j且y_i < y_j$ 或者 $x_i > x_j 且 y_i > y_j$ .问最多能挑出多少物品.

进阶：时间复杂度 $O(nlogn)\$ ，空间复杂度 $O(n)\$

第一行输入一个正整数.表示有组数据.
对于每组数据,第一行输入一个正整数.表示物品个数.
接下来两行,每行有个整数.
第一行表示个节点的属性.
第二行表示个节点的属性.

输出行,每一行对应每组数据的输出.

示例1

输入

2
3
1 3 2
0 2 3
4
1 5 4 2 
10 32 19 21

2
3

算法知识视频讲解

暂无题解

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师阿里巴巴测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师信息技术岗区块链测试开发工程师大数据开发工程师数据分析师 Java工程师

上传者：小小

难度：

35条回答 644收藏 16775浏览

扫一扫，把题目装进口袋