#P3375. [Usaco2004 Mar]Paranoid Cows 发疯的奶牛
[Usaco2004 Mar]Paranoid Cows 发疯的奶牛
[USACO 2004 Mar] Paranoid Cows 发疯的奶牛
题目描述
约翰有 头奶牛,编号为 到 。奶牛们不希望别人知道自己的产奶量。约翰安排第 头奶牛在时刻 进入奶棚挤奶,在时刻 离开。奶棚的门很窄,同一时刻只能容一头奶牛进出。
若对两头不同的奶牛 有 ,则称这两个时间段嵌套。此时奶牛 在奶牛 挤奶的整个过程中都在奶棚里,可以窥知奶牛 的产奶量。
求最大的 ,使编号 到 的奶牛中没有两个时间段嵌套。
输入格式
从标准输入读入。第一行是整数 ,接下来 行,每行两个整数 ,依次为第 头奶牛进入和离开奶棚的时刻。
输出格式
向标准输出输出一行一个整数 。
5
7 20
1 4
3 12
6 10
0 3
3
样例解释
第 头奶牛的时间段 被第 头的 严格包含,前 头奶牛之间没有嵌套。
数据范围与约定
,。嵌套按题面所列的严格不等式判定。