Chương trình tìm số khóa học tối đa có thể học theo khoảng thời gian trong Python

Cho danh sách khoảng thời gian times = [[start, end], ...] đại diện cho giờ bắt đầu và kết thúc của các khóa học. Chỉ được học một khóa tại một thời điểm, và khóa tiếp theo phải bắt đầu sau khi khóa trước kết thúc (start > end trước). Tìm số khóa học tối đa có thể học.

Ví dụ

Đầu vào: [[3, 6], [6, 9], [7, 8], [9, 11]]

Chọn: [3,6] → [7,8] → [9,11] → kết quả: 3.

Thuật toán (Greedy - Sắp xếp theo thời gian kết thúc)

1. Sắp xếp danh sách theo end tăng dần.
2. Khởi tạo count = 0, last_end = -1.
3. Duyệt qua các khóa học đã sắp xếp:
   • Nếu start > last_end: chọn khóa này, count++, last_end = end.
4. Trả về count.

Triển khai Python

class Solution:
    def solve(self, times):
        # Sắp xếp theo thời gian kết thúc
        times.sort(key=lambda x: x[1])
        count = 0
        last_end = -1
        for start, end in times:
            if start > last_end:
                count += 1
                last_end = end
        return count

# Test
ob = Solution()
times = [[3, 6], [6, 9], [7, 8], [9, 11]]
print(ob.solve(times))  # Output: 3

Độ phức tạp

• Thời gian: O(n log n) do sắp xếp.
• Không gian: O(1) thêm (ngoài input).

Đây là bài toán kinh điển "Activity Selection" / "Interval Scheduling".