‹ 上一题 下一题 ›

g5-09044. 监控探头 未做

1000 ms 256 MB 测试点 10 通过率 100% GESP-55级·贪心经典模型区间调度与选择阶梯·运用

题目描述

一条直街上有 家店铺,第 家需要监控它门前从第 米到第 米的一段路(两端米数也算在范围内)。一个监控探头可以立在任何整数位置上,能照管所有包含这个位置的店铺路段。

最少立几个探头,能让每家店铺的路段都被照到?

输入格式

第一行一个整数 。接下来 行,每行两个整数 。

输出格式

一行一个整数:最少探头数。

样例

输入
3
1 3
2 5
4 7
输出
2

样例解释

在 米处立一个探头: 在 和 内,前两家都被照到;再在 米处立一个照到第三家。一个探头不够,因为没有位置能同时落在 和 …也没有位置同时落在三条路段里。

数据范围

,。

输入
输出

            
答案