THÁCH THỨC 01: Bố trí phòng họp

Có N cuộc họp đánh số từ 0 đến N-1 đăng ký làm việc tại một phòng hội thảo. Cuộc họp i cần bắt đầu vào thời điểm A[i] và kết thúc vào thời điểm B[i] (i=0,1,2,...,N-1). Hai cuộc họp có thể nhận phục vụ nếu các khoảng thời gian làm việc tương ứng của chúng chỉ có thể giao nhau tại đầu mút hoặc tách rời nhau. Hãy tìm một lịch cho phòng hội thảo để có thể phục vụ nhiều cuộc họp nhất.

Dữ liệu vào từ file Activity.inp gồm:

• Dòng đầu tiên ghi số cuộc họp được đăng ký N (N <= 500 000 000)

• Dòng thứ i trong N dòng tiếp theo ghi 2 thời gian bắt đầu A[i] và thời gian kết thúc B của cuộc họp i, A[i] B[i] cách nhau ít nhất một dấu cách. (0 <= A[i], B[i] < 1 000 000)

Kết quả: Ghi ra file Activity.out gồm

• Dòng đầu tiên ghi k là số cuộc họp tối đa có thể bố trí

• Dòng tiếp theo ghi số hiệu của cuộc họp được phục vụ theo trình tự lịch bố trí

Ví dụ:

Code:

ACTIVITY.INP      ACTIVITY.OUT
5                  3
0 2                0 3 4
1 3
0 5
2 4
6 8