区间不相交问题
- 给出n个开区间，从中选出尽可能区间，使这些区间两两之间没有交集
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 30;
//给出n个开区间，从中选出尽可能区间，使这些区间两两之间没有交集
//按照右端点排序 当右端点一样时 按照左端点升序排序
struct duan
{
int x, y;
};
bool cmp(duan a, duan b)
{
return a.y != b.y ? a.y < b.y : a.x < b.x;
}
int main()
{
duan duans[maxn];
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d%d", &duans[i].x, &duans[i].y);
}
sort(duans, duans + n, cmp);
int ans = 0;
int cnt = 0;
while (cnt < n)
{
ans++;
cnt++;
while (cnt<n&&duans[cnt].x <= duans[cnt - 1].x)
{
cnt++;
}
}
printf("%d
", ans);
}