Bài 17.2. Xếp Lịch Hội Thảo Tối Ưu - [Độ khó: Khá]

Bạn đang làm việc cho một trung tâm tổ chức sự kiện và nhiệm vụ của bạn là tối ưu hóa việc sử dụng một phòng hội thảo duy nhất. Bạn được cung cấp danh sách các buổi nói chuyện (hoạt động) tiềm năng, mỗi buổi có thời gian bắt đầu và thời gian kết thúc cụ thể. Mục tiêu của bạn là xác định số lượng buổi nói chuyện tối đa mà phòng hội thảo có thể tổ chức mà không có bất kỳ sự chồng chéo nào. Một buổi nói chuyện chỉ có thể bắt đầu sau khi buổi nói chuyện trước đó đã kết thúc (ngay cả khi thời gian kết thúc của buổi trước trùng với thời gian bắt đầu của buổi sau, thì buổi sau vẫn có thể diễn ra).

INPUT FORMAT

Dòng đầu tiên chứa một số nguyên dương N (1 <= N <= 10^5) - số lượng buổi nói chuyện. N dòng tiếp theo, mỗi dòng chứa hai số nguyên S và E (0 <= S < E <= 10^9) - thời gian bắt đầu và thời gian kết thúc của một buổi nói chuyện.

OUTPUT FORMAT

In ra một số nguyên duy nhất là số lượng buổi nói chuyện tối đa có thể tổ chức.

Ví dụ:

Input:

6
1 3
2 5
0 6
5 7
3 8
5 9

Output:

3

Giải thích: Các buổi nói chuyện là: (1,3), (2,5), (0,6), (5,7), (3,8), (5,9). Để tối ưu hóa, chúng ta nên sắp xếp các buổi nói chuyện theo thời gian kết thúc tăng dần. Các buổi sau khi sắp xếp theo thời gian kết thúc:

1. (1,3)
2. (2,5)
3. (0,6)
4. (5,7)
5. (3,8)
6. (5,9)

Áp dụng thuật toán tham lam:

• Chọn buổi đầu tiên có thời gian kết thúc sớm nhất: (1,3). Buổi tiếp theo phải bắt đầu từ 3 trở đi.
• Duyệt qua các buổi còn lại. Buổi đầu tiên có thời gian bắt đầu >= 3 là (5,7). Chọn (5,7). Buổi tiếp theo phải bắt đầu từ 7 trở đi.
• Duyệt qua các buổi còn lại. Buổi đầu tiên có thời gian bắt đầu >= 7 là không có.
• Vậy, số buổi tối đa có thể chọn là 2: (1,3) và (5,7).

Lưu ý: Ví dụ trên là một trường hợp để minh họa. Trong thực tế, có thể có nhiều cách chọn khác nhau. Ví dụ nếu chọn (1,3), (5,9) thì không có 3 buổi. Nếu danh sách đã sắp xếp là (1,3), (2,5), (0,6), (5,7), (3,8), (5,9):

• Chọn (1,3). current_end = 3.
• Tiếp theo, tìm buổi có start >= 3. Buổi (5,7) là ứng viên đầu tiên. Chọn (5,7). current_end = 7.
• Tiếp theo, tìm buổi có start >= 7. Không có. -> Số buổi = 2.

Cập nhật giải thích và ví dụ để ra output 3: Sắp xếp theo thời gian kết thúc tăng dần:

• (1,3)
• (2,5)
• (0,6)
• (5,7)
• (3,8)
• (5,9)

1. Chọn buổi (1,3). last_finish_time = 3. Số buổi = 1.
2. Duyệt các buổi còn lại. Buổi (2,5) bắt đầu tại 2 < 3, bỏ qua. Buổi (0,6) bắt đầu tại 0 < 3, bỏ qua.
3. Buổi (5,7) bắt đầu tại 5 >= 3. Chọn (5,7). last_finish_time = 7. Số buổi = 2.
4. Duyệt các buổi còn lại. Buổi (3,8) bắt đầu tại 3 < 7, bỏ qua. Buổi (5,9) bắt đầu tại 5 < 7, bỏ qua.
5. Không còn buổi nào có thể chọn.

Vậy số buổi tối đa là 2. Có vẻ ví dụ ban đầu của tôi bị lỗi, output là 3. Cần chỉnh lại input hoặc output của ví dụ. Nếu input là:

6
1 3
2 4
3 5
0 6
5 7
6 8

Sắp xếp theo kết thúc: (1,3), (2,4), (3,5), (0,6), (5,7), (6,8)

1. Chọn (1,3). last_finish_time = 3. Count = 1.
2. Tiếp theo, chọn (3,5). last_finish_time = 5. Count = 2.
3. Tiếp theo, chọn (5,7). last_finish_time = 7. Count = 3.
4. Tiếp theo, chọn (6,8). last_finish_time = 8. Count = 4. Output = 4.

Để đạt output 3 với ví dụ ban đầu, tôi phải chọn các buổi như sau: (1,3), (5,7), (3,8) là không đúng vì (5,7) và (3,8) chồng chéo. Cách để ra 3 buổi: (1,3) -> end = 3 (3,?) -> (3,8) -> end = 8 (8,?) -> Không có

Cách khác: (0,6) -> end = 6 (6,?) -> Không có

Cách khác: (2,5) -> end = 5 (5,7) -> end = 7 (7,?) -> Không có

Đây là một ví dụ phổ biến với output 3: Input:

3
10 20
12 25
20 30

Sắp xếp theo kết thúc: (10,20), (12,25), (20,30)

1. Chọn (10,20). last_finish_time = 20. Count = 1.
2. Tiếp theo, (20,30) bắt đầu tại 20 >= 20. Chọn (20,30). last_finish_time = 30. Count = 2. Output = 2.

Tôi sẽ sử dụng ví dụ đơn giản và rõ ràng hơn cho output 3.

Ví dụ mới cho Bài 17.2: Input:

5
1 4
3 5
0 6
5 7
8 9

Output:

3

Giải thích: Các buổi nói chuyện là: (1,4), (3,5), (0,6), (5,7), (8,9). Sắp xếp các buổi theo thời gian kết thúc tăng dần:

1. (1,4)
2. (3,5)
3. (0,6)
4. (5,7)
5. (8,9)

Áp dụng thuật toán tham lam (greedy algorithm):

• Bước 1: Chọn buổi đầu tiên có thời gian kết thúc sớm nhất: (1,4). Số buổi được chọn hiện tại là 1. Thời gian kết thúc của buổi cuối cùng được chọn là 4.
• Bước 2: Duyệt các buổi còn lại. Buổi tiếp theo hợp lệ là buổi có thời gian bắt đầu lớn hơn hoặc bằng thời gian kết thúc của buổi cuối cùng đã chọn (tức là >= 4). Buổi (3,5) bắt đầu lúc 3, nhỏ hơn 4, bỏ qua. Buổi (0,6) bắt đầu lúc 0, nhỏ hơn 4, bỏ qua. Buổi (5,7) bắt đầu lúc 5, lớn hơn hoặc bằng 4. Chọn buổi (5,7). Số buổi được chọn hiện tại là 2. Thời gian kết thúc của buổi cuối cùng được chọn là 7.
• Bước 3: Tiếp tục duyệt các buổi còn lại. Buổi (8,9) bắt đầu lúc 8, lớn hơn hoặc bằng 7. Chọn buổi (8,9). Số buổi được chọn hiện tại là 3. Thời gian kết thúc của buổi cuối cùng được chọn là 9.
• Bước 4: Không còn buổi nào để chọn.

Vậy, số lượng buổi nói chuyện tối đa có thể tổ chức là 3. Các buổi được chọn là (1,4), (5,7), và (8,9).