XẾP PHÒNG

Có n cuộc hội thảo (đánh số từ 1 tới n) đăng ký sử dụng phòng của khu nhà do bạn quản lý. Cuộc hội thảo thứ i bắt đầu ngay sau thời điểm s_i và kết thúc tại thời điểm f_i. Có thể hiểu thời gian cuộc hội thảo tứ i diễn ra là một khoảng (s_i, f_i] trên trục thời gian. Hãy bố trí các phòng phục vụ toàn bộ các cuộc hội thảo thỏa mãn các yêu cầu sau:

+ Tại mỗi thời điểm, mỗi phòng chỉ dùng cho một cuộc hội thảo. Hay nói cách khác, hai cuộc hội thảo chỉ có thể bố trí trong cùng một phòng nếu khoảng thời gian làm việc của chúng không giao nhau.

+ Số phòng cần huy động để phục vụ cho toàn bộ n cuộc hội thảo là ít nhất có thể.

Dữ liệu vào: Từ tệp văn bản ROOMS.INP

+ Dòng 1 chứa số nguyên dương n ≤10⁵

+ n dòng tiếp theo, dòng thứ i chứa hai số tự nhiên s_i, f_i. (s_ii

≤10⁵)

Kết quả: ghi ra tệp văn bản ROOMS.OUT

+ Dòng 1 ghi số lượng phòng cần huy động (k)

+ K dòng tiếp theo, dòng thứ j ghi chỉ số các cuộc hội thảo sẽ được tổ chức tại phòng thứ j trong k dãy phòng đã huy động

Ví dụ:

ROOMS.INP	ROOMS.OUT
4 0 2 2 4 1 3 3 5	2 1 2 3 4