Làm thế nào để giải quyết bài toán Interval Scheduling (Lên lịch khoảng thời gian) bằng Greedy Algorithms nhằm tối ưu hóa việc phân bổ tài nguyên phòng họp trong hệ thống Enterprise?

Question

Accepted Answer

Bản chất bài toán
Cho một danh sách các cuộc họp, mỗi cuộc họp có thời gian bắt đầu (Start time) và thời gian kết thúc (End time). Một phòng họp chỉ có thể tổ chức một cuộc họp tại một thời điểm. Hãy tìm số lượng cuộc họp tối đa có thể tổ chức thành công trong phòng họp đó.
Chiến lược Greedy chuẩn xác

Sắp xếp toàn bộ các khoảng thời gian theo thứ tự tăng dần của thời gian kết thúc (End Time).
Chọn cuộc họp đầu tiên trong danh sách đã sắp xếp vì nó kết thúc sớm nhất, giải phóng phòng họp nhanh nhất.
Duyệt qua các cuộc họp tiếp theo, chỉ chọn cuộc họp nào có thời gian bắt đầu lớn hơn hoặc bằng thời gian kết thúc của cuộc họp vừa được chọn gần nhất.

Ví dụ cài đặt bằng JavaScript
function maxMeetings(intervals) {
    // Sắp xếp theo thời gian kết thúc tăng dần
    intervals.sort((a, b) => a.end - b.end);

let selectedMeetings = [];
    if (intervals.length === 0) return selectedMeetings;

// Luôn chọn cuộc họp đầu tiên kết thúc sớm nhất
    selectedMeetings.push(intervals[0]);
    let lastEndTime = intervals[0].end;

for (let i = 1; i < intervals.length; i++) {
        if (intervals[i].start >= lastEndTime) {
            selectedMeetings.push(intervals[i]);
            lastEndTime = intervals[i].end;
        }
    }

return selectedMeetings;
}
Lưu ý kinh nghiệm thực chiến

Nhiều lập trình viên Junior thường mắc sai lầm là sắp xếp theo thời gian bắt đầu hoặc sắp xếp theo khoảng thời gian ngắn nhất (Duration). Cả hai cách này đều sai và không đảm bảo tối ưu toàn cục. Việc sắp xếp theo thời gian kết thúc là chìa khóa duy nhất mang lại tính đúng đắn cho thuật toán Greedy trong bài toán này.

Làm thế nào để giải quyết bài toán Interval Scheduling (Lên lịch khoảng thời gian) bằng Greedy Algorithms nhằm tối ưu hóa việc phân bổ tài nguyên phòng họp trong hệ thống Enterprise?

Bản chất bài toán

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi greedy algorithms liên quan cùng chủ đề