差分数组

#include<iostream>
#include<cmath>
using namespace std;
//差分数组
int de[10010];//初始化为0，表示某个第i个整数点于第i-1个整数点相比挖树次数的差值；
int l,m;
int main(){
    cin>>l>>m;
    int x,y;
    for(int i=0;i<m;i++){
        cin>>x>>y;
        if(x>y) swap(x,y);//交换坐标值
        de[x]++;
        de[y+1]--;
    }
    int c=0,a=0;
    for(int j=0;j<=l;j++){
        a=a+de[j];//得到每一个点挖数次数
        if(a==0) c++;
    }
    cout<<c;
    return 0;
} 

标记法

#include <stdio.h>

int main() {
    int a[10010] = {0};
    int m, n;
    scanf("%d %d", &m, &n);
    while (n > 0) {
        int x1, x2;
        scanf("%d %d", &x1, &x2);
        for (int i = x1; i <= x2; i++) {
            a[i] = 1;
        }
        n--;

    }
    int acc = 0;
    for (int i = 0; i <= m; i++) {
        if (a[i] == 0) {
            acc++;
        }
    }
    printf("%d", acc);
    return 0;
}

合并区间

#include<iostream>
#include<cmath>
using namespace std;
int de[10010];
int l,m;
int main(){
	cin>>l>>m;
	int x,y;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		if(x>y) swap(x,y);
		de[x]++;
		de[y+1]--;
	}
	int c=0,a=0;
	for(int j=0;j<=l;j++){
		a=a+de[j];
		if(a==0) c++;
	}
	cout<<c;
	return 0;
}