XẾP PHÒNG THI TRONG MỘT OLYMPIC TIN HỌC SINH VIÊN, CÓ N CUỘC TH...

Bài 1. Xếp phòng thi

Trong một Olympic Tin học sinh viên, có N cuộc thi được đánh số hiệu từ 1 đến N. Cuộc thi

thứ i có thời điểm bắt đầu S

i

và thời điểm kết thúc F

i

. Tại mỗi thời điểm trong mỗi phòng thi

có không quá một cuộc thi diễn ra, ngoại trừ trường hợp thời điểm kết thúc một cuộc thi có

thể đồng thời là thời điểm bắt đầu của một cuộc thi khác.

Yêu cầu:

Hãy xếp phòng thi cho tất cả các cuộc thi sao cho số phòng cần sử dụng là ít nhất.

Dữ liệu: Vào từ file văn bản ROOMS.INP theo qui cách như sau:



Dòng thứ nhất ghi số nguyên dương N (N≤ 1000) là số lượng cuộc thi.



Trên dòng thứ i (1 ≤ i ≤ N) trong N dòng tiếp theo ghi hai số nguyên dương S

i

và

F

i

(0 ≤ S

i

< F

i

≤ 70000) tương ứng là thời điểm bắt đầu và thời điểm kết thúc của

cuộc thi i.

Kết quả: Ghi ra file văn bản ROOMS.OUT một số nguyên M là số phòng ít nhất cần cho các

cuộc thi.

ROOMS.INP

ROOMS.OUT

5

2

0 2

1 2

3 4

2 5

4 5