408006: GYM102961 T Room Allocation

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

T. Room Allocationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There is a large hotel, and $$$n$$$ customers will arrive soon. Each customer wants to have a single room.

You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.

What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?

Input

The first input line contains an integer $$$n$$$: the number of customers.

Then there are $$$n$$$ lines, each of which describes one customer. Each line has two integers $$$a$$$ and $$$b$$$: the arrival and departure day.

Constraints:

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

Print first an integer $$$k$$$: the minimum number of rooms required.

After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered $$$1,2,\dots,k$$$. You can print any valid solution.

ExampleInput
3
1 2
2 4
4 4
Output
2
1 2 1

加入题单

上一题 下一题 算法标签: