Phân phòng tối thiểu

Bối cảnh và bài toán

Một khách sạn có n lượt khách, mỗi lượt chiếm phòng từ ngày a đến hết ngày b. Hai khách có thể dùng cùng phòng chỉ khi khách trước rời vào ngày nhỏ hơn ngày khách sau đến (b_prev < a_next).

Yêu cầu

Tìm số phòng tối thiểu và gán số phòng cho từng khách theo thứ tự input.

Input

• Dòng 1: n.
• n dòng: a b.

Output

Dòng 1 in số phòng. Dòng 2 in phòng của từng khách theo thứ tự input.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= a <= b <= 10^9

Chấm điểm

Ví dụ 1

Input

3
1 2
2 4
4 4

Output

2
1 2 1

Giải thích. Khách 1 và 2 chồng ngày 2 nên cần hai phòng; phòng 1 trống trước ngày 4 nên khách 3 dùng lại.

Ví dụ 2

Input

4
1 1
2 2
3 3
4 4

Output

1
1 1 1 1

Giải thích. Mỗi khách đến sau khi khách trước đã rời nên một phòng đủ.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set – Room Allocation.

Tham khảo: https://new.cses.fi/problemset/task/1164