题目描述
给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。只有当c<=a 且 b<=d 时，我们才认为区间[a,b]被区间[c,d]覆盖。在完成所有删除操作后，请你返回列表中剩余区间的数目。
输入格式
第一行输入一个整数n，代表有n个区间。以下n行，每行输入两个整数L，R，L代表区间左边界，R代表区间右边界。
输出格式
输出一个整数，代表列表中剩余区间的数目。
样例
Input 1
3 1 4 3 6 2 8
Output 1
2
样例解释
第一个区间[1,4]不能被其他区域覆盖，第三个区间[3,6]被[2,8]覆盖
数据范围
1<=n<=1000; 0<=l,r<=1e5; 不会存在相同的区间。
#include<bits/stdc++.h>
using namespace std;
struct node {
int l, r;
}A[1005];
bool AC(node a, node b) {
return b.l <= a.l && a.r <= b.r;
}
int wa(vector<node>& nodes) {
sort(nodes.begin(), nodes.end(),
[](const node& a, const node& b) { return a.l < b.l; });
set<int> re;
int ans = 0;
for (const auto& node : nodes) {
if (!re.count(node.l)) {
ans++;
re.insert(node.r);
}
}
return ans;
}
int main() {
int n;
cin >> n;
vector<node> nodes(n);
for (int i = 0; i < n; ++i) {
cin >> A[i].l >> A[i].r;
}
cout << wa(A[n]) << endl;
return 0;
}