区间选点

区间选点

题目描述

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式
第一行包含整数N，表示区间数。

接下来N行，每行包含两个整数 ai,bi表示一个区间的两个端点。

输出格式
输出一个整数，表示所需的点的最小数量。

数据范围
1≤N≤105
−109≤ai≤bi≤109

输入样例

1
2
3
4
3
-1 1
2 4
3 5

输出样例

1
2

思路

略：
按区域的右端点进行排序
如果区域内没有点，就把区域的右端点作为点
如果有点，那就进行下一个
详：
1.首先，该代码定义了一个结构体 Range，它包含两个成员：l 和 r，分别代表区间的左端点和右端点。这个结构体还定义了一个比较函数，使得我们可以按照右端点对 Range 对象进行排序。
2.在 main 函数中，首先通过 scanf 函数读取一个整数 n，表示区间的数量。
3.然后，程序读入 n 对区间，每对区间通过 scanf 函数读入，并存储到 range 数组中。
4.接着，程序使用 STL 的 sort 函数对 range 数组进行排序。排序的依据是每个区间的右端点。
5.排序后，程序通过一个循环来统计连续区间的数量。变量 res 用来存储这个数量，变量 ed 表示当前已经遍历的区间的右端点。如果遇到一个区间的左端点大于 ed（也就是说，这个区间与之前的区间不连续），那么就将 res 增加 1，并将 ed 更新为当前区间的右端点。
6.最后，程序通过 printf 函数输出 res，即连续区间的数量。

注意事项

在比较函数中，使用了 < 运算符。在 C++ 中，对于自定义的结构体或者类，如果你要定义 < 运算符，那么你需要同时定义 > 运算符。否则，编译器会因为找不到对称的运算符而报错。这里只定义了 < 运算符，但因为结构体 Range 的成员是整型，所以编译器会自动补全 > 运算符。但如果你自定义的结构体包含复杂类型（例如字符串或者自定义类）作为成员，那么你就需要自己定义完整的 < 和 > 运算符了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int n;
struct Randge
{
	int l,r;
	//方法重载进行右端点的排序 
	bool operator<(const Randge &W)const
	{
		return r<W.r;
	}
}range[N];
int main(){
	scanf("%d",&n);
	//循环输入区间 
	for(int i=0;i<n;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		//将区间的左右端点存入结构体 
		range[i]={l,r};
	 } 
	 //将结构体里的右端点进行排序 
	sort(range,range+n); 
	//定义 点的数量，以及最开始的判断区间的点的坐标
	//因为第一个点肯定是最小区间的右端点，res要加1
	//所以把ed设为无穷小 
	int res=0;int ed=-2e9;
	//循环遍历每一个右端点
	//如果这个右端点小于选定的点，无事发生
	//如果不是，res++，ed更换为这个右端点
	for(int i=0;i<n;i++){
		if(range[i].l>ed){
			res++;
			ed=range[i].r;
		}
	} 
	
	printf("%d\n",res);
	return 0;
}