Bố trí Phòng Khách sạn

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Một khách sạn cần bố trí phòng cho $n$ khách. Hai khách có thể ở chung một phòng nếu ngày rời đi của khách thứ nhất thực sự sớm hơn ngày đến của khách thứ hai. Hãy tìm số phòng tối thiểu cần dùng và gán mỗi khách vào một phòng.

Dữ liệu vào

Dòng đầu: số nguyên $n$ — số lượng khách.
$n$ dòng tiếp theo, dòng thứ $i$ : hai số nguyên $a_{i}$ và $b_{i}$ — ngày đến và ngày rời đi của khách $i$ ( $1 \leq a_{i} \leq b_{i} \leq 10^{9}$ ).

Dữ liệu ra

Dòng 1: số nguyên $k$ — số phòng tối thiểu cần dùng.
Dòng 2: $n$ số nguyên (từ 1 đến $k$ ) — phòng được gán cho mỗi khách theo thứ tự đầu vào.

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$
$1 \leq a_{i} \leq b_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
3 1 2 2 4 4 4	2 1 2 1	Khách 1 rời ngày 2, khách 3 đến ngày 4. Vì 2 < 4, họ có thể ở chung phòng 1. Khách 2 cần phòng riêng.
4 1 3 2 5 4 6 3 4	2 1 1 2 2	Khách 1 rời ngày 3, khách 4 đến ngày 3. Vì 3 không < 3, họ không thể ở chung.

Bình luận

Không có bình luận tại thời điểm này.