本文主要是介绍Q - 区间相交问题 FZU - 1230，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定 x 轴上 n 个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交。
★算法设计： 对于给定的 n 个闭区间，计算去掉的最少闭区间数。
Input
对于每组输入数据，输入数据的第一行是正整数 n (1<=n<=40,000)，表示闭区间数。接下来的 n 行中，每行有 2 个整数，分别表示闭区间的 2 个端点。
Output
输出计算出的去掉的最少闭区间数。
Sample Input
3 10 20 15 10 20 15
Sample Output
2 解题思路：简单的贪心，，把所有的区间按右端点的值从小到大排序，然后遍历从小到大，如果后一个的左端点小于等于前一个右端点，则要去掉这个区间。注意输入是要使区间的左边都小于右边，如果输入的值不是需要把他们交换。
代码如下：
#include<stdio.h>
#include<algorithm>
using namespace std;
struct note
{int st,en;
} e[40100];
bool cmp(note x,note y) //按照右区间从小到大排序
{if(x.en==y.en) return x.st<y.st;elsereturn x.en<y.en;
}
int main()
{int n;while(~scanf("%d",&n)){int a,b,i;for(i=0; i<n; i++){scanf("%d%d",&a,&b);if(a>b) //如果左端点大于右端点交换左右的值{int c=a;a=b;b=c;}e[i].st=a;e[i].en=b;}sort(e,e+n,cmp); //排序int k=0,sum=0;for(i=1;i<n;i++){if(e[i].st<=e[k].en) //如果左端点小于等于前一个的右端点sum++; //去掉这个区间.else k=i;}printf("%d\n",sum);}return 0;
}
这篇关于Q - 区间相交问题 FZU - 1230的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
