[牛客小白月赛12]A.华华听月月唱歌（贪心 + 双指针）

题目传送门：A-华华听月月唱歌_牛客小白月赛12 (nowcoder.com)

思路 / Thought

既然是区间题，看一眼数据范围，N到了1e9，所以肯定要用vector将区间左右端点存下来处理。

先将所有区间按照左端点排序，然后用双指针每次向右拓展最大距离，如果最后右端点能够到达N，说明可以拼凑成功。

r表示从1可以到达的最远连续右端。

代码 / Code

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, M;cin >> N >> M;
	
	vector<pair<int, int> > v, t;
	for(int i = 1;i <= M; ++ i)
	{
		int x, y;cin >> x >> y;
		v.push_back({x, y});
	}
	sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b){return a.fi < b.fi;});
	
	int r = 0, ans = 0;//r表示可以连续到达的最右位置 
	for(int i = 0;i < M && r < N;)
	{
		int j = i, tr = 0;
		while(j < M && v[j].fi <= r + 1)tr = max(tr, v[j ++].se);
		if(tr <= r)break;//说明无法连接起来
		r = tr, i = j, ans ++;
	}
	
	cout << (r < N ? -1 : ans) << '\n'; 
	
	return 0;
}