本文主要是介绍week3 B-区间选点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）
输入输出：
Input：第一行1个整数N（N<=100）
第2~N+1行，每行两个整数a,b（a,b<=100）
output：一个整数，代表选点的数目
解题思路：
这里选点的贪心算法是先对区间进行排序，按照右端点升序，左端点降序，排完序后，遍历每个区间，如果没有选点在该区间内，则选取该区间的右端点为选点，直到所有区间都有选点为止。证明思路：排好序后，对于每一个区间，选取右端点是最有利的，因为最受到后面区间的欢迎。
实验代码：
#include<iostream>
#include<algorithm>
using namespace std;
struct qujian
{int l;int r;bool operator<(const qujian& q) const{if(r!=q.r) //先按右端点升序,左端点降序 return r<q.r;elsereturn l>q.l;}
};
int main(void)
{int n;cin>>n;qujian q[100];for(int i=0;i<n;i++){cin>>q[i].l>>q[i].r;}sort(q,q+n);//排序 int end=q[0].r;int k=1,point=1; //point为选点,k为区间索引 while(k<n) //考察每个区间 {if(q[k].l>end) {end=q[k].r;point++;// k++;}k++;} cout<<point<<endl;return 0;
}
这篇关于week3 B-区间选点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
