A.華華聽月月唱歌

鏈接：https://ac.nowcoder.com/acm/contest/392/A

題意：

月月唱歌超級好聽的說！華華聽說月月在某個網站發布了自己唱的歌曲，于是把完整的歌曲下載到了U盤里。然而華華不小心把U盤摔了一下，里面的文件摔碎了。月月的歌曲可以看成由1到N的正整數依次排列構成的序列，它現在變成了若干個區間，這些區間可能互相重疊。華華想把它修復為完整的歌曲，也就是找到若干個片段，使他們的并集包含1到N（注意，本題中我們只關注整數，見樣例1）。但是華華很懶，所以他想選擇最少的區間。請你算出華華最少選擇多少個區間。因為華華的U盤受損嚴重，所以有可能做不到，如果做不到請輸出-1。

思路：

左端點排序，從左端點最多超出當點右端點1的段中選右端點最遠的。

判斷是否能覆蓋全部端點。

代碼：

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int MAXN = 1e5 + 10;struct Node
{int _l;int _r;bool operator < (const Node & that) const{return this->_l < that._l;}
}node[MAXN];int main()
{int n, m;scanf("%d%d", &n, &m);for (int i = 1;i <= m;i++)scanf("%d%d", &node[i]._l, &node[i]._r);sort(node + 1, node + 1 + m);int l = 0, r = 0, res = 0, len = 0;int flag = 1;for (int i = 1;i <= m;i++){if (node[i]._l <= r + 1){len = max(len, node[i]._r - r);continue;}if (len == 0){flag = 0;break;}r = r + len;len = 0;res++;i--;//cout << r << endl;if (r >= n){len = 0;break;}}if (len > 0){r += len;res++;}if (!flag || r < n)printf("-1\n");elseprintf("%d\n", res);return 0;
}