ACM模版

描述

题解

区间合并问题。水题……

代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 111;
const int INF = 0x3f3f3f3f;

struct interval
{
    int l, r;
} Itv[MAXN];

int L, M;

bool cmp(interval a, interval b)
{
    if (a.l == b.l)
    {
        return a.r < b.r;
    }
    return a.l < b.l;
}

int main(int argc, const char * argv[])
{
    cin >> L >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> Itv[i].l >> Itv[i].r;
    }

    sort(Itv, Itv + M, cmp);
    for (int i = 1; i < M; i++)
    {
        if (Itv[i].l <= Itv[i - 1].r && Itv[i].r >= Itv[i - 1].r)
        {
            Itv[i].l = Itv[i - 1].l;
            Itv[i - 1].l = INF;
        }
        else if (Itv[i].r <= Itv[i - 1].r)
        {
            Itv[i].r = Itv[i - 1].r;
            Itv[i].l = Itv[i - 1].l;
            Itv[i - 1].l = INF;
        }
    }
    sort(Itv, Itv + M, cmp);

    int res = L + 1;
    for (int i = 0; i < M; i++)
    {
        if (Itv[i].l > L)
        {
            break;
        }
        res -= min(L - Itv[i].l + 1, Itv[i].r - Itv[i].l + 1);
    }

    cout << res << '\n';

    return 0;
}