问题 2205. -- 畜栏预定 Stall Reservation

2205: 畜栏预定 Stall Reservation

时间限制: 1 Sec  内存限制: 128 MB
提交: 12  解决: 7
[提交][状态][讨论版]

题目描述

有N头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草,所以可能会需要多个畜栏。
给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B,每头牛在[A,B]这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时(包括端点),这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目。

输入

第1行:输入一个整数N。
第2..N+1行:第i+1行输入第i头牛的开始吃草时间A以及结束吃草时间B,数之间用空格隔开。

输出

一个整数,代表所需最小畜栏数。

样例输入

5
1 10
2 4
3 6
5 8
4 7

样例输出

4

提示

数据范围:1≤N≤50000, 1≤A,B≤1000000

来源

[提交][状态]