C++14(g++5.4) 解法, 执行用时: 104ms, 内存消耗: 1144K, 提交时间: 2019-03-10 14:30:08

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
pair<int,int>pn[N];
 int n,m,le,k,num;
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++)
	cin>>pn[i].first>>pn[i].second;
	sort(pn,pn+m);
	le=1;k=0;num=0;
	while(le<=n){
		int res=0;
		while(pn[k].first<=le&&k<=m)
			res=max(res,pn[k].second),k++;
		if(res>=le)
			le=res+1,num++;
		else{
			num=-1;
			break;
		}
	}
	cout<<num<<endl;
	return 0;
}

Python3 解法, 执行用时: 713ms, 内存消耗: 32484K, 提交时间: 2023-05-15 16:11:34

n, m = map(int, input().split())
arr = []
for _ in range(m):
    arr.append(list(map(int, input().split())))
    
arr.sort(key=lambda x:(x[0], x[1]))
res = 0
tmp = 0
i = 0
while i<m and tmp<n:
    if arr[i][0] > tmp +1:
        break
    endmax = tmp
    while i<m and arr[i][0]<=tmp+1:
        endmax = max(endmax, arr[i][1])
        i += 1
    res += 1
    tmp = endmax
if tmp<n:
    print(-1)
else:
    print(res)

C++(clang++ 11.0.1) 解法, 执行用时: 32ms, 内存消耗: 1196K, 提交时间: 2023-07-30 16:01:54

#include<iostream>
using namespace std;
int main(){
	int n,m,i,j,x=1,x1,y=0;
	int l[100010],r[100010];
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d %d",&l[i],&r[i]);
	while(1){
		x1=0;
		if(x>n) break;
		y++;
		for(i=1;i<=m;i++)
			if(x>=l[i]&&x<=r[i]&&r[i]>=x1) x1=r[i]+1;
		x=x1;
		if(x1==0) {
			printf("-1");
			return 0;
		}
	}
	printf("%d",y);
	return 0;
}