问题2149--最大化器（POJ1769）

2149: 最大化器（POJ1769）

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

公司正在准备一个新的分拣硬件，称之为最大化器。最大化器的n 个输入都从1到n ，每个输入都代表一个整数。最大化器有一个输出，代表输入的最大值。最大化器的实现为排序器(i1 , j1 ), …, 排序器(ik , jk )的流水线。每台排序器都有n 个输入和n 个输出。排序器(i , j )对输入i , i +1, …, j 以非递减顺序输出，对其他输入原样输出。最后一个排序器的第n 个输出是最大化器的输出。经过观察，去掉一些排序器之后，最大化器仍然可以产生正确的结果。给定排序器序列，求可以产生正确结果的最少排序器数量。

输入

输入的第1行包含两个整数n 和m （2≤n ≤50000，1≤m≤500000），分别表示输入的数量和流水线中的排序器数量。接下来的m 行描述排序器的初始顺序，第k 行包含第k 个排序器的参数，即两个整数s 和t （1≤s <t ≤n ），表示排序器排序的范围。

输出

单行输出可以产生正确结果的最少排序器数量。

样例输入 Copy 

40 6
20 30
1 10
10 20
20 30
15 25
30 40

样例输出 Copy 

4

来源/分类

动态规划算法 线段树 
[提交] [状态]