Bài toán 1: Bố trí phòng họp

Phát biểu bài toán

Có n cuộc họp. Cuộc họp thứ i bắt đầu vào thời điểm a_i và kết thúc ở thời điểm b_i.

Do chỉ có một phòng hội thảo, nên hai cuộc họp bất kì chỉ có thể cùng được bố trí nếu khoảng thời gian làm việc của chúng không giao nhau hoặc chỉ giao nhau tại đầu mút.

Hãy bố trí phòng họp sao cho phục vụ được nhiều cuộc họp nhất.

Dữ liệu vào

Đọc từ file văn bản BTPH.INP:

• Dòng 1 ghi số nguyên dương N (1 ≤ N ≤ 1000).
• N dòng tiếp theo, dòng thứ i chứa hai số nguyên dương a_i, b_i (1 ≤ a_i ≤ b_i ≤ 1000) là thời điểm bắt đầu và kết thúc của cuộc họp thứ i.

Dữ liệu ra

Ghi ra file văn bản BTPH.OUT:

• Một số nguyên duy nhất là số cuộc họp nhiều nhất có thể bố trí.

Ràng buộc

• 1 ≤ N ≤ 1000
• 1 ≤ a_i ≤ b_i ≤ 1000

Chấm điểm

• Subtask 1 (30 điểm): 1 ≤ N ≤ 20
• Subtask 2 (30 điểm): 1 ≤ N ≤ 200
• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.

Ví dụ

BTPH.INP

4
4 5
5 6
1 6
6 9

BTPH.OUT

3

Giải thích

Có thể chọn 3 cuộc họp:

• (4, 5)
• (5, 6)
• (6, 9)

Ba cuộc họp này không chồng lấn nhau, chỉ chạm nhau tại đầu mút.

Gợi ý

Đây là bài toán chọn nhiều đoạn thời gian nhất sao cho các đoạn không giao nhau.

Ý tưởng tối ưu:

• Sắp xếp các cuộc họp theo thời điểm kết thúc tăng dần
• Luôn chọn cuộc họp kết thúc sớm nhất có thể mà vẫn hợp lệ