熬兔笥

题面描述

时间限制 ：1s 空间限制：256MB
有$n$只兔子，它们排成一排，下面有$m$个操作

操作$l,r$表示在区间l到r上，每只兔子上面盖上一个熬兔笥

下面你可以用你的力量，每次对$n$只兔子都删除一个熬兔笥，问最少进行几次操作。

输入格式

一行两个数$n,m$表示有$n$个元素，有$m$次区间覆盖

接下来$m$行每行两个整数$l.r$表示覆盖的区间

输出格式

一行一个整数，表示最少删除几次

样例1

输入

10 1
1 10

输出

1

样例2

输入

10 2
1 5
6 10

输出

1

样例3

输入

10 3
1 5
6 10
4 7

输出

2

数据范围

对于30%的数据,$n,m<=1000$

对于60%的数据,$n<=10^6,m<=1000$

对于100%的数据 $n<=10^9,m <= 10^5$

30分

暴力模拟

60分

线段树区间加，求最大值
或者差分给一段区间加，求序列最大值

100分-1

离散化，做线段树，求全局最大值

100分-2

（也是我本来想的解法，被差分吊打了）
两个区间有交就是，一个区间的左端点被完整包含在另一个区间里
这个问题可以转化成某个区间最多和几个区间有交，只对左端点最靠后的一个区间统计
用按照左端点顺序往set里加线段，set里按照右端点排序，弹出所有右端点大于当前线段左端点的线段，然后每次ans对set的大小取max

100分-3

离散化，差分给一段区间加，求序列最大值

考试情况

给24的高一做，A掉这题的全写的第一个做法……
0分30分60分100分均匀分布（是的……A掉的人数只有4,5个……）