Toggle navigation
首页
讨论版
入门知识
题库
状态
排名
竞赛&作业
下载
Login
问题 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
来源
贪心/堆
[
提交
][
状态
]