题解 | #值周#

贪心 时间复杂度 O(mlogm)

• 对给定区间进行左端点排序
• 将具有交集部分的区间划分成整体， 并计算出此区间长度
• 最总答案 ： $n+1n+1$ $--$ $\mathrm{\Sigma }\mathrm{非}\mathrm{交}\mathrm{集}\mathrm{区}\mathrm{间}\mathrm{长}\mathrm{度}\backslash Sigma非交集区间长度$

#include <iostream>

using namespace std;

const int N = 1000010;

typedef pair<int,int> PII;

PII p[N];


int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; ++ i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        p[i] = {x, y};
    }
    sort(p, p + m);
    int res = 0, start = p[0].first, r = 0;
    for (int i = 1; i < m; ++ i)
    {
        if (p[i].first > p[r].second)
        {
            res += p[r].second - start + 1;
            start = p[i].first;
        }
        if (p[i].second > p[r].second)   r = i;
    }
    res += p[r].second - start + 1;
    printf("%d\n", n + 1 - res);
    
    return 0;
}