蓝桥杯 ALGO-986 藏匿的刺客(贪心)

试题 算法训练 藏匿的刺客

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　 强大的kAc建立了强大的帝国，但人民深受其学霸及23文化的压迫，于是勇敢的鹏决心反抗。
　kAc帝国防守森严，鹏带领着小伙伴们躲在城外的草堆叶子中，称为叶子鹏。
　kAc帝国的派出的n个看守员都发现了这一问题，第i个人会告诉你在第li个草堆到第ri个草堆里面有人，要求你计算所有草堆中最少的人数，以商议应对。
　“你为什么这么厉害”，得到过kAc衷心赞美的你必将全力以赴。

输入格式

　　第一行两个整数N,M。
　　一行N个整数，表示木棍的长度。

输出格式

　　输出一个数，表示最少人数。

样例输入

5
2 4
1 3
5 7
1 8
8 8

样例输出

数据规模和约定

　30%的数据n<=10
　70%的数据n<=100
　100%的数据n<=1000
　所有数字均在int表示范围内

思路：

1. 将每个区间按右端点排序

2. 将最小的右端点和下一个区间的左端点比较，若左端点小于右端点，说明两区间重合，只要在该右端点记一个人即可

3. 若左端点大于右端点，说明两区间未重合，需要再记一个人，并且更新最小右端点为该区间的右端点

4. 遍历所有区间

要点：

1. 排序
2. 记最多的区间能重合的点

代码：

#include 

using namespace std;
const int N = 1010;
struct Range{
	int l , r;

	bool operator<(const Range &w) const{
		return r < w.r;
	}
}range[N];

int n;

int main(){
	cin >> n;
	
	for (int  i = 0 ; i < n ; i ++ )
		cin >> range[i].l >> range[i].r;

	sort(range, range + n);
    
	int minr = range[0].r;
	
    int res = 1;
    for (int i = 1; i < n ; i ++)
        if (range[i].l > minr){
            res ++;
            minr = range[i].r;
        }

	cout << res << endl;

	return 0;
}

吐槽：

none