区间选点详解

步骤

operator<  的作用在 C++ 中， operator<  是一个运算符重载函数，它定义了如何比较两个对象的大小。在  std::sort  函数中，它会用到这个比较函数来决定排序的顺序。

在 sort  中，默认会使用  <  运算符来比较两个对象的大小。如果对象是基本类型（如  int 、 float  等）， <  运算符的含义是明确的。但如果对象是一个自定义类型（如这里的  Range  结构体），我们需要明确地告诉 sort  如何比较两个  Range  对象的大小。

通过重载  <  运算符，我们定义了  Range  对象之间的比较规则。在这个问题中，我们希望按照区间的右端点  r  来排序，因此我们定义了比较规则为：如果一个区间的右端点  r  小于另一个区间的右端点  r ，则认为这个区间“小于”另一个区间。

AC代码：

#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n;
struct Range//定义一个结构体，一个结构体代表一个区间
{int l, r;bool operator< (const Range &W)const//由于要排序，所以重载一下{return r < W.r;//按照右端排序}
}range[N];int main()
{cin>>n;for (int i = 0; i < n; i ++ ) cin>>range[i].l>>range[i].r;sort(range, range + n);
//从左往右扫描int res = 0, ed = -2e9;//res代表当前选择的点数，ed代表上一个点的右下标for (int i = 0; i < n; i ++ )if (range[i].l > ed){res ++ ;ed = range[i].r;}cout<<res;return 0;
}