#P3375. [Usaco2004 Mar]Paranoid Cows 发疯的奶牛

    ID: 2565 传统题 1000ms 512MiB 尝试: 36 已通过: 22 难度: 4 上传者: 标签>难度分类普及排序与序列处理二分答案前后缀最值CF1400Orange

[Usaco2004 Mar]Paranoid Cows 发疯的奶牛

[USACO 2004 Mar] Paranoid Cows 发疯的奶牛

题目描述

约翰有 NN 头奶牛,编号为 11 到 NN。奶牛们不希望别人知道自己的产奶量。约翰安排第 ii 头奶牛在时刻 AiA_i 进入奶棚挤奶,在时刻 BiB_i 离开。奶棚的门很窄,同一时刻只能容一头奶牛进出。

若对两头不同的奶牛 i,ji,j 有 Ai<Aj<Bj<BiA_i<A_j<B_j<B_i,则称这两个时间段嵌套。此时奶牛 ii 在奶牛 jj 挤奶的整个过程中都在奶棚里,可以窥知奶牛 jj 的产奶量。

求最大的 KK,使编号 11 到 KK 的奶牛中没有两个时间段嵌套。

输入格式

从标准输入读入。第一行是整数 NN,接下来 NN 行,每行两个整数 Ai,BiA_i,B_i,依次为第 ii 头奶牛进入和离开奶棚的时刻。

输出格式

向标准输出输出一行一个整数 KK。

5
7 20
1 4
3 12
6 10
0 3
3

样例解释

第 44 头奶牛的时间段 (6,10)(6,10) 被第 33 头的 (3,12)(3,12) 严格包含,前 33 头奶牛之间没有嵌套。

数据范围与约定

1≤N≤100 0001\le N\le 100\,000,0≤Ai<Bi≤1090\le A_i<B_i\le 10^9。嵌套按题面所列的严格不等式判定。