题目性质：1.当前节点空闲则必须做任务，而不是可选可不选；2.然而前面的如果能覆盖当前节点，就可以不选。

解决方法：倒着扫可以很好地解决这两个问题。dp[i]为时刻i可得的最大空闲时间。如果此刻没有任务，则空闲时间+1；否则最大空闲时间等于任务结束节点的最大空闲时间：

 1     vector<int> dp(n + 2, 0);
 2     int cnt = k - 1;
 3     irep(i, n, 1) {
 4         if (cnt < 0 || a[cnt].first != i) {
 5             dp[i] = dp[i + 1] + 1;
 6         } else {
 7             while (~cnt && a[cnt].first == i) {
 8                 dp[i] = max(dp[a[cnt--].second], dp[i]);
 9             }
10         }
11     }

总代码main：

 1 int main() {
 2     read(n), read(k);
 3     vector<P> a;
 4     rep(i, 1, k) {
 5         int x, y;
 6         read(x), read(y);
 7         a.push_back(P(x, x + y));
 8     }
 9     sort(a.begin(), a.end());
10     vector<int> dp(n + 2, 0);
11     int cnt = k - 1;
12     irep(i, n, 1) {
13         if (cnt < 0 || a[cnt].first != i) {
14             dp[i] = dp[i + 1] + 1;
15         } else {
16             while (~cnt && a[cnt].first == i) {
17                 dp[i] = max(dp[a[cnt--].second], dp[i]);
18             }
19         }
20     }
21     writeln(dp[1]);
22     return 0;
23 }