AcWing 422. 校门外的树
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-02-10 23:25:26
,
所有人可见
,
阅读 254
/*#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int L, n;
bool st[N];
int main() {
scanf("%d%d", &L, &n);
for(int i = 0; i <= L; i ++) st[i] = true;
//下面来读入n个区间
while (n --) {
int a, b;
scanf("%d%d", &a, &b);
//将a到b之间的部分设置为false
for (int i = a; i <= b; i ++) {
st[i] = false;
}
}
//最后来统计一下有多少个位置上是true;
int res = 0;
for (int i = 0; i <= L; i ++) res += st[i];
printf("%d\n", res);
return 0;
}
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
//使用结构体来存储空间
struct Segment{
int l, r;
//此时需要来按照l的长度来进行排序, 所以此时需要俩重载< 符号
bool operator< (const Segment& t) const {
return l < t.l;
}
}seg[N];
int m, n;
int main() {
//读入所有的树
scanf("%d%d", &m, &n);
// for (int i = 0; i < n; i ++) scanf("%d%d", seg[i].l, seg[i].r);
for (int i = 0; i < n; i ++) cin >> seg[i].l >> seg[i].r;
// //将所有的区间进行排序
sort(seg, seg + n);
//使用sum来表示所有的区间的总长度
int sum = 0;
int L = seg[0].l, R = seg[0].r;
//开始从第二个区间开始来进行遍历
for (int i = 1; i < n; i ++) {
if (seg[i].l <= R) {
R = max(R, seg[i].r);
} else {
//否则此时产生了一个新的区间
sum += R - L + 1;
L = seg[i].l, R = seg[i].r;
}
}
sum += R - L + 1;
printf("%d", m + 1 - sum);
}