暴力模拟不用多说,这里讲别的方法。
此题可以看成括号匹配问题。
假设起点为左括号,终点为右括号。
<----------[=====>====]
可以等价为
<----------[=====]---->
然后就是括号匹配了。
C++ 代码
#include<iostream>
using namespace std;
int main(){
int l,n;
int ll[10001]={0},rl[10001]={0};
cin>>l>>n;
int tl,tr;
for(int i=1;i<=n;i++){
cin>>tl>>tr;
ll[tl]++;
rl[tr]++;
}
int top=0,cnt=0;
for(int i=0;i<=l;i++){
if(!ll[i] && !rl[i] && !top) cnt++;
top+=ll[i];
top-=rl[i];
}
cout<<cnt;
}