蓝桥杯 算法训练 藏匿的刺客

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

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

输入格式

　　第一行一个数字n，接下来2到n+1行，每行两个数li和ri，如题。

输出格式

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

样例输入

5
2 4
1 3
5 7
1 8
8 8

样例输出

3

数据规模和约定

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

思路：

        贪心，对右端点进行排序，并记录最小右端点的值，last_min 如果下一个数据的左端点大于last_min,则人数必须加一，且要更新最小右端点last_min，否则两个区间有重合，只需要算last_min处的一个人即可；

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10;
int n,m,t,d;
int a[N],b[N];
string s;
map<int,int>mp;
signed main(){
	cin>>n;
	t = n;
	int x,y;
	int idx = 0;
	while(t--){
		cin>>x>>y;
		mp[y] = x;
		a[idx++] = y;
	}
	sort(a,a+n);
	int last_min = a[0];
	int people = 1;
	for(int i=1;i<n;i++){
		if(mp[a[i]]>last_min){
			people++;
			last_min = a[i];
		}
	}
	cout<<people<<endl;	
	return 0;
}