题解

提供一种使用最短路算法的做法。

由于 $M$ 范围太大，先将所有时间离散化。

先假设没有 $s_i\gt e_i$ 的情况，此时有一种经典的建图方法：

• 对于所有的 $i \in [1,N]$，从 $s_i$ 向 $e_i$ 连一条权值为 $1$ 的边。
• 对于所有的 $i \in [1,M]$，从 $i$ 向 $i-1$ 连一条权值为 $0$ 的边。

答案即为 $0$ 到 $M$ 的最短路。

（正确性证明就不讲了，请自行理解）

再考虑 $s_i\gt e_i$ 的情况：（为了方便，下文称其为上夜班）

若拆成 $(0,e_i)$ 和 $(s_i,M)$ 两条边，我们会发现会有重复统计的情况。

于是可以将每个边 $(0,e_i)$ 标记颜色 $i$，跑最短路的同时维护每个点的颜色 $col_u$，表示点 $u$ 的最短路需要经过颜色为 $col_u$ 的边。

统计答案时，枚举每个上夜班的人 $i$，若 $col_{s_i}=i$，说明 $i$ 在之前已经统计过了，答案为 $dis_i$，否则答案为 $dis_i+1$。

时间复杂度 $O(n \log n)$。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5,M=8e5+5,inf=1e9;
int n,m,tot,siz,ans=inf;
int s[N],t[N];
int dis[N],col[N],vis[N];
vector<int>v;
struct edg{
	int v,w,nxt,col;
}e[M];
int head[N];
void add(int u,int v,int w,int col){
	e[++tot].v=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
	e[tot].col=col;
}
struct A{
	int u,dis;
};
bool operator <(const A &x,const A &y){
	return x.dis>y.dis;
}
void dijk(int s){
	for(int i=0;i<=m;i++)dis[i]=inf;
	dis[s]=0;
	priority_queue<A>q;
	q.push(A{s,0});
	while(!q.empty()){
		A x=q.top();q.pop();
		vis[x.u]=1;
		for(int i=head[x.u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w,c=e[i].col;
			if(vis[v])continue;
			if(dis[x.u]+w<dis[v]){
				dis[v]=dis[x.u]+w;
				col[v]=max(col[x.u],c);
				q.push(A{v,dis[v]});
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&s[i],&t[i]);//t[i]即为题目的e[i] 
		v.push_back(s[i]);
		v.push_back(t[i]);
	}
	v.push_back(0);
	v.push_back(m);
	sort(v.begin(),v.end());
	siz=unique(v.begin(),v.end())-v.begin();
	for(int i=1;i<=n;i++){
		s[i]=lower_bound(v.begin(),v.begin()+siz,s[i])-v.begin();
		t[i]=lower_bound(v.begin(),v.begin()+siz,t[i])-v.begin();
	}
	m=lower_bound(v.begin(),v.begin()+siz,m)-v.begin();
	for(int i=1;i<=n;i++){
		if(s[i]<t[i])add(s[i],t[i],1,0);
		else if(s[i]>t[i]){
			add(0,t[i],1,i);
		}
	}
	for(int i=0;i<m;i++)add(i+1,i,0,0);
	dijk(0);
	ans=dis[m];//有可能没有人上夜班 
	for(int i=1;i<=n;i++){
		if(s[i]<=t[i])continue;
		ans=min(ans,dis[s[i]]+(col[s[i]]!=i));
	}
	if(ans>=inf)cout<<-1;
	else cout<<ans;
	return 0;
}/*
*/