CSES - Room Allocation | Bố trí phòng
Xem PDF
Điểm:
1300
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có một khách sạn lớn, và \(n\) khách hàng sẽ đến sớm. Mỗi khách hàng muốn có một phòng đơn.
Bạn biết ngày nhận phòng và trả phòng của mỗi khách hàng. Hai khách hàng có thể ở trong cùng một phòng nếu ngày trả phòng của khách hàng đầu tiên sớm hơn ngày nhận phòng của khách hàng thứ hai.
Số lượng phòng tối thiểu cần thiết để chứa tất cả khách hàng là bao nhiêu? Và các phòng có thể được phân bổ như thế nào?
Input
- Dòng đầu vào đầu tiên chứa một số nguyên n: số lượng khách hàng.
- Sau đó, có \(n\) dòng, mỗi dòng mô tả một khách hàng. Mỗi dòng có hai số nguyên \(a\) và \(b\): ngày nhận phòng và trả phòng.
Output
- In đầu tiên một số nguyên \(k\): số phòng tối thiểu cần thiết.
- Sau đó, in một dòng chứa số phòng của mỗi khách hàng theo thứ tự giống như trong đầu vào. Các phòng được đánh số \(1,2,\ldots,k\). Bạn có thể in bất kỳ giải pháp hợp lệ nào.
Constraints
- \(1 \le n \le 2 \cdot 10^5\)
- \(1 \le a \leq b \le 10^9\)
Example
Sample input
3
1 2
2 4
4 4
Sample output
2
1 2 1
Bình luận
chưa có checker phải không admin? em nộp qua cses ac rồi qua đây wa
bài đây zễ òm
bth mà có zì đâu
Checker đã có từ đầu. Nếu bạn vẫn tiếp tục gặp vấn đề, bạn vui lòng tạo ticket nêu rõ hơn nhé. Cảm ơn bạn.
ổng cũng AC từ đó rồi
hồi 2022 rồi mà
giống mình
Checker đã có từ đầu. Nếu bạn vẫn tiếp tục gặp vấn đề, bạn vui lòng tạo ticket nêu rõ hơn nhé. Cảm ơn bạn.
Checker đã có từ đầu. Nếu bạn vẫn tiếp tục gặp vấn đề, bạn vui lòng tạo ticket nêu rõ hơn nhé. Cảm ơn bạn.