Analysis
首先，如果一个时间只有一个任务开始，则她必须做。如果一个时间有多个任务开始，她可以选一个去做。我们发现这样的决策是取决于后面的空暇时间，而不是前面。所以在dp的时候需要从后往前搜时间（当然如果从前往后可以跑记搜）
考虑转移，如果一个时间有多个任务开始，则选一个空暇时间最长的，如果一个时间没有任务开始，则空暇时间=上一个时间的空暇时间+1，我们本次转移只是如果到了这个时间，已产生的最大空闲时间，显然不一定会用到，但是我们还是要转移，因为我们并不知道会不会用到。
形式化地，若设\(f_i\)表示后\(i\)个时间地最大空闲时间，则：
\(f_i=max(f_i+last_i)\) （满足\(i\)是一个任务的起点，\(f_i+last_i\)表示该任务的终点，显然如果做这个任务则这个任务中间的空暇时间都不能用了，一定是取终点的空暇时间。
\(f_i=f_{i+1}+1\) （满足\(i\)不是一个任务的起点，用上一步+1进行转移）
具体实现的时候为了方便，可以对任务的开始时间进行排序，设置一个\(pos\)记录当前搜到了哪个任务，由于我们保证任务是有序的，所以\(pos\)的开始时间一定是当前的开始时间，实现的时候更加简便。
至此，本题得解，具体实现见代码。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100100
using namespace std;
int n,k;
int f[N];
int vis[N];
struct Node
{
int start,end;
}qwq[N];
bool cmp(Node a,Node b)
{
return a.start > b.start; //按照start time从大到小排序，因为我们是倒着搜的
}
int num = 1; //pos
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&qwq[i].start,&qwq[i].end);
vis[qwq[i].start] ++; //记录当前时间的start time数量
}
sort(qwq+1,qwq+k+1,cmp); //从大到小对任务排序
for(int i=n;i>=1;i--) //倒着搜
{
if(!vis[i]) f[i] = f[i+1]+1; //如果当前时间没有任务开始则用上一步转移
else
{
for(int j=1;j<=vis[i];j++)//当前时间有vis_i个任务
{
f[i] = max(f[i],f[i+qwq[num].end]); //状态转移在上文已解释
num++; //pos++
}
}
}
cout<<f[1]<<endl; //由于我们是倒着转移的，所以输出也要倒着f_1
return 0;
}