← 返回题目列表

Codeforces · 597/B

B. 餐厅

中文机器翻译题面 查看原题

一家餐厅收到 n 个租赁订单。每个租赁订单都会在连续一段时间内预订餐厅,第 i 个订单由两个时间值来表征 - 开始时间 li 和结束时间 ri (li ≤ ri)。

餐厅管理层可以接受和拒绝订单。餐厅最多可以接受多少订单?

两个已接受的订单不能相交,即它们不能共享哪怕是片刻的时间。如果一个订单在另一个订单开始时结束,则不能同时接受这两个订单。

输入

第一行包含整数 n (1 ≤ n ≤ 5·105) — 订单数。以下 n 行分别包含整数值 li 和 ri (1 ≤ li ≤ ri ≤ 109)。

输出

打印可以接受的最大订单数。

示例

输入 #1

2
7 11
4 7

输出 #1

1

输入 #2

5
1 2
2 3
3 4
4 5
5 6

输出 #2

3

输入 #3

6
4 8
1 5
4 7
2 5
1 3
6 8

输出 #3

2