<span style="font-family: Tahoma, Arial, sans-serif, simsun; background-color: rgb(255, 255, 255);">描述</span>
上数学课时,老师给了LYH一些闭区间,让他取尽量少的点,使得每个闭区间内至少有一个点。但是这几天LYH太忙了,你们帮帮他吗?
- 输入
- 多组测试数据。
每组数据先输入一个N,表示有N个闭区间(N≤100)。
接下来N行,每行输入两个数a,b(0≤a≤b≤100),表示区间的两个端点。 -
输出
输出一个整数,表示最少需要找几个点。
这题很简单,只要每次都记录好公共区域的坐标就好了(是排序后进行的遍历)
#include<iostream> #include<algorithm> using namespace std; struct Node{ int left; int right; }node[105]; int cmp(struct Node a,struct Node b){ return a.left<b.left; } int min(int a,int b){ return a<b?a:b; } int main(){ int n,i; int begin,end; while(cin>>n){ for(i=0;i<n;i++){ cin>>node[i].left>>node[i].right; } sort(node,node+n,cmp); begin=node[0].left; end=node[0].right; //begin,end 代表着公共区域的距离 int sumb=1; for(i=1;i<n;i++){ if(node[i].left>end){ sumb++; begin=node[i].left; end=node[i].right; } else{ begin=node[i].left; end=min(end,node[i].right); } } cout<<sumb<<endl; } return 0; }