这题是思维考察。由于区间个数可能会很多，暴力完全没法下手。首先要明确区间长度最小的就决定了最后的答案，因为最小区间必须要要从0开始到区间长度减1才能满足让mex最大。接下来就是考虑如何填充数组才能让所有区间的mex大于等于最小区间的mex，暴力根本没法下手，我是直接考虑最短区间，比他更长的区间如果覆盖了比它更短的区间那么更长区间的mex一定大于等于短区间的mex，直接让数组所有的长度为最短区间长度的区间的mex成为最大最小mex，就可以得到答案了。
AC代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
const int inf=1<<30;
int res[maxn];
int main(){
int n,m,cnt;
while(scanf("%d%d",&n,&m)!=EOF){
cnt=inf;
int x,y;
for(int i=0;i<m;++i){
scanf("%d%d",&x,&y);
cnt=min(cnt,y-x+1); //计算最短区间长度
}
for(int i=0;i<n;++i){
res[i]=i%cnt; //填充数组
}
printf("%d\n",cnt);
for(int i=0;i<n;++i){
if(i==n-1) printf("%d\n",res[i]);
else printf("%d ",res[i]);
}
}
return 0;
}
其实数组完全可以省略。
如有不当之处欢迎指出！