题目描述

给定了一个长度为n的区间，再给出m条线段的左端点和右端点，问最少使用多少条线段可以将整个区间覆盖。区间的范围为[1,n]。

输入格式

第一行输入n,m。n的范围是[1,1000000],m的范围是[1,100000]分别表示区间长度和线段数量。后面2到m+1行输入区间，每行2个数，分别表示区间的左端点和右端点。

输出格式

如果能覆盖，就输出覆盖所需的最小线段数，否则输出-1。

输入输出样例：

10 3
1 7
3 6
6 10

2

---

我的代码：

#include <bits/stdc++.h>
#define I return
#define AK 0
#define IOI ;
#define ll long long
using namespace std;
const ll N = 1e7 + 5;
int a[N], dp[N], n, m, x, y, l, r, ans;
inline ll read()
{ // 快读
    ll x = 0, y = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        y = (c == 45) ? -1 : 1;
        c = getchar();
    }
    while (isdigit(c))
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar();
    }
    return x * y;
}
inline void out(ll x)
{
    if (x < 0)
    {
        x = ~(x - 1);
        putchar('-');
    }
    if (x > 9)
        out(x / 10);
    putchar(x % 10 + '0');
}
inline void write(ll x, char ch)
{ // 快输
    out(x);
    putchar(ch);
}
int main()
{
    m = read(), n = read();
    for (int i = 1; i <= n; i++)
    {
        l = read(), r = read();
        a[l] = max(a[l], r);
    }
    int j = 1, k = a[1], maxn = 1;
    while (k < m)
    {
        for (int i = j; i <= k; i++)
        {
            if (a[i] > a[maxn])
                maxn = i;
        }
        if (maxn == j)
        {
            cout << -1;
            I AK IOI
        }
        else
            ans++;
        j = maxn, k = a[maxn];
    }
    out(ans + 1);
    I AK IOI
}

有 bug，求调