#23. 畜栏预定
畜栏预定
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
有头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草,所以可能会需要多个畜栏。
给定头牛和每头牛开始吃草的时间以及结束吃草的时间B,每头牛在这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时(包括端点),这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
输入格式
第1行:
输入一个整数。
第2..N+1行:
第行输入第头牛的开始吃草时间以及结束吃草时间,数之间用空格隔开。
输出格式
第1行:
输入一个整数,代表所需最小畜栏数。
第2..N+1行:
第行输入第头牛被安排到的畜栏编号,编号是从开始的 连续 整数,只要方案合法即可。
spj
样例
输入数据
5
1 10
2 4
3 6
5 8
4 7
输出数据
4
1
2
3
2
4
提示