Room Allocation

题目描述

有一家大型旅馆，接下来会有 n 位顾客到达。每位顾客都想要一间单人房。 你知道每位顾客的到达与离开日期。如果第一位顾客的离开日期早于第二位顾客的到达日期，则两位顾客可以住同一间房。 需要最少多少间房来容纳所有顾客？并且如何分配房间？

输入格式

第一行包含一个整数 n：顾客的数量。 接下来有 n 行，每行描述一位顾客。每行包含两个整数 a 和 b：到达日和离开日。

输出格式

首先输出一个整数 k：所需的最小房间数。 之后输出一行，包含按照输入顺序每位顾客的房间编号。房间编号为 1,2,$\ldots$,k。你可以输出任意一个满足条件的解。

3
1 2
2 4
4 4

2
1 2 1

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le a \le b \le 10^9$

标签: CSES1164|排序和搜索

来源

CSES1164|排序和搜索