🧑‍🤝‍🧑 俱乐部邀请问题

📘 题目描述

俱乐部共有 NN 位会员，每位会员都拥有两个属性：

• A_i：表示​强壮值​；
• B_i：表示​美丽值​。

这些会员虽然优秀，但都有一个缺点——​容易嫉妒​。若会员 i 和会员 j 满足以下任一条件，i 就会嫉妒 j：

• Ai≤Aj 且 Bi≥Bj
• Ai≥Aj且 Bi≤Bj

但如果 j 的两个值都小于 i，那么 i 会忽视他；如果 j 的两个值都大于 i，那么 i 会尊敬他。

为了防止争斗，俱乐部经理希望选出一组互不嫉妒的会员，参加舞会。请你计算，最多可以邀请多少位会员。

📥 输入格式

• 第一行一个整数 $N（2≤N≤10^5$），表示会员数；
• 接下来 NN 行，每行两个整数 $A\_i, B\_i$（$1 \le A\_i, B\_i \le 10^9$），表示第 i 位会员的属性。

📤 输出格式

• 输出一个整数，表示最多可以邀请的会员数量。

📌 输入样例

4
3 2
2 1
5 5
1 2

📌 输出样例

3

🧠 解题思路

本质分析：

本题的核心是构造一个满足特定关系的​最大子序列​。为了保证不嫉妒，需选择一组会员，使得他们之间​不存在上述两种嫉妒关系​。

可以使用“二维偏序 + LIS（最长递增子序列）”解决。

做法：

1. 将会员按 A 升序排序，若 A 相同则按 B 降序排序；
2. 在排序后的 B 序列上，寻找最长​严格递增子序列​；
3. 答案即为最长 LIS 的长度。

排序原因：

• 由于嫉妒关系涉及 AA 和 BB，我们需要打破二者的对称性；
• 使用 (A ↑, B ↓) 排序后，若直接求 B 的 LIS，就能避免重复 A 的情况下错误计入序列。