5347. 房间分配（Room Allocation）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 有一家大型酒店，即将迎来 $n$ 位顾客。每位顾客都需要一间单人房。 你知道每位顾客的入住和退房日期。如果第一位顾客的退房日期早于第二位顾客的入住日期，则两位顾客可以入住同一间客房。请问最少需要多少间客房才能容纳所有顾客？应该如何分配客房？ ## 输入格式 第一行包含一个整数 $n$，表示顾客的数量。 接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$，分别表示顾客的入住和退房日期。 ## 输出格式 第一行输出一个整数 $k$，表示所需的最少客房数量。 第二行输出 $n$ 个整数，依次表示每位顾客分配到的房间编号（房间编号为 $1, 2, \dots, k$）。你可以输出任意合法方案。 ## 输入输出样例 ### 输入 #1 ``` 3 1 2 2 4 4 4 ``` ### 输出 #1 ``` 2 1 2 1 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n \le 2 \cdot 10^5$ - $1 \le a \le b \le 10^9$