7375: BZOJ3375:[Usaco2004 Mar]Paranoid Cows 发疯的奶牛
Memory Limit:128 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
约翰有N(1≤N≤100000)头奶牛,它们都可以控制自己的产奶量.一头产奶不多的奶牛会被其它奶牛嘲笑, 约翰制订一张产奶时间表,第i头奶牛在Ai_Bi时间段里产奶(0≤Ai<Bi≤10^9).这头奶牛必须在Ai的时候进入奶棚在Bi的时候离开.奶棚的门很小,同一时刻只能有一头奶牛通过. 如果第i头奶牛产奶的时间段包含第j头奶牛产奶的时间段,即A<Aj<Bj<Bi.那么,我们称这两个时间段是“巢段”. “巢段”是一件很糟糕的事,因为第j头奶牛在奶棚的时间里第i头奶牛一直都在.这样第i头奶牛就能估计第j头奶牛的产奶量.由于产奶量被别的奶牛知道了的奶牛会发疯,所以约翰不希望“巢段”的发生. 帮助约翰确定最大的k(1≤K≤N),在1到K的奶牛中不存在“巢段”.
输入格式
第1行:奶牛的数量N. 第2到N+1行:每行有两个用空格隔开的数字,表示这头奶牛的产奶时间段.
输出格式
一个整数K
样例输入
5 7 20 1 4 3 12 6 10 0 3
样例输出
3 样例说明 第4头奶牛( 6-10)被包含于第3头奶牛(3-12).另外,1至3头奶牛不存在“巢段”
提示
没有写明提示
题目来源
Orange