THỜI GIAN LÀM VIỆC CỦA MÁY TÍNH N MÁY TÍNH CÓ SỐ HIỆU 1,..,N...
Bài 1. 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; a
i
, b
i
nguyên dương, a
i
<b
i
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 một 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, mỗi dòng 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 một máy tính (ghi cách nhau ít nhất là một 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 của 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 một 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ụ:
Tệp THOIGIAN.INP
Tệp THOIGIAN.OUT
8
5
2 3
1
4 5
2
10 12
7
3
13 15
1 9
4
2 5
6 8
7 15