Question

[Hoàng Lê Anh Tài]

Bài 2: Thời gian làm việc của máy tính.

N máy tính có số hiệu 1..N thực hiện N chương trình. Thời gian thực hiện chương trình của máy tính có số hiệu i là từ thời điểm thời gian a_i đến thời điểm thời gian b_i (1<N<=1000, ai, bi nguyên dương, ai<bi<=2000). Hãy xác định nhiều nhất các khoảng thời gian thực hiện chương trình của các máy tính sao cho không có thời điểm thời gian nào trùng nhau. Mỗi khoảng thời gian tìm được là chỉ bao gồm các thời điểm thời gian thực hiện chương trình của 1 máy tính.

Dữ liệu vào là tệp văn bản THOIGIAN.INP có cấu trúc:

- Dòng đầu tiên ghi số N

- N dòng tiếp theo ghi thời điểm thời gian bắt đầu và thời điểm thời gian kết thúc việc thực hiện chương trình của 1 máy tính (ghi cách nhau ít nhất là 1 ký tự trống). Thông tin về khoảng thời gian thực hiện chương trình của các máy tính được ghi tuần tự theo thứ tự tăng dần số hiệu của các máy tính đó.

Dữ liệu ra là tệp văn bản THOIGIAN.OUT có cấu trúc:

- Dòng đầu tiên ghi số lượng các khoảng thời gian tìm được.

- Các dòng tiếp theo ghi số hiệu của các máy tính có các khoảng thời gian tìm được. Mỗi số hiệu ghi trên 1 dòng và số hiệu của máy tính nào có khoảng thời gian với các thời điểm thời gian bắt đầu, thời điểm thời gian kết thúc chương trình nhỏ hơn thì được ghi trước.

Ví dụ:

THOIGIAN.INP	THOIGIAN.OUT
8 2 3 4 5 10 12 13 15 1 9 2 5 6 8 7 15	5 1 2 7 3 4