#23. 畜栏预定

畜栏预定

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

N\red{N}头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草,所以可能会需要多个畜栏。

给定N\red{N}头牛和每头牛开始吃草的时间A\red{A}以及结束吃草的时间B,每头牛在[A,B]\red{[A,B]}这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时(包括端点),这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式

第1行:输入一个整数N\red{N}

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

输出格式

第1行:输入一个整数,代表所需最小畜栏数。

第2..N+1行:i+1\red{i+1}行输入第i\red{i}头牛被安排到的畜栏编号,编号是从1\red{1}开始的 连续 整数,只要方案合法即可。

本题目有本题目有spj

样例

输入数据

5
1 10
2 4
3 6
5 8
4 7

输出数据

4
1
2
3
2
4

提示

1N50000,\red{1≤N≤50000,}

1A,B1000000\red{1≤A,B≤1000000}

国庆j组4

未参加
状态
已结束
规则
OI
题目
4
开始于
2021-10-4 17:00
结束于
2021-10-4 23:00
持续时间
6 小时
主持人
参赛人数
6