Thuật toán Interval Scheduling là gì? Giải thích dễ hiểu kèm demo chọn số cuộc họp nhiều nhất

Thuật toán Interval Scheduling là gì? Giải thích dễ hiểu kèm demo chọn số cuộc họp nhiều nhất

Trong thực tế, lịch làm việc của chúng ta thường đầy các cuộc họp chồng chéo nhau. Nếu chỉ có một phòng họp (hoặc một người tham gia được) thì câu hỏi đặt ra là: làm sao chọn được nhiều cuộc họp nhất mà không bị trùng giờ? Đây chính là bài toán Interval Scheduling kinh điển: cho một danh sách các khoảng thời gian (cuộc họp), hãy chọn ra tập con có nhiều cuộc họp nhất sao cho chúng không giao nhau.

Trong bài viết này, chúng ta sẽ:

• Hiểu bài toán Interval Scheduling trong ngữ cảnh thực tế (sắp xếp cuộc họp).
• Nắm được ý tưởng greedy: luôn chọn cuộc họp kết thúc sớm nhất.
• Thấy tại sao chiến lược này lại cho nghiệm tối ưu.
• Xem demo trực quan trên một trục thời gian bằng JavaScript.

Bài toán Interval Scheduling là gì?

Giả sử bạn có một phòng họp và một danh sách các cuộc họp, mỗi cuộc họp được mô tả bởi:

• Thời gian bắt đầu start.
• Thời gian kết thúc end.

Mỗi lúc chỉ có thể diễn ra một cuộc họp trong phòng. Mục tiêu là chọn ra nhiều cuộc họp nhất mà không có cuộc nào bị trùng thời gian.

Ví dụ, các cuộc họp (tính theo giờ):

• A: 1 – 4
• B: 3 – 5
• C: 0 – 6
• D: 5 – 7
• E: 8 – 9

Rõ ràng không thể tham gia tất cả, vì nhiều cuộc họp chồng lên nhau. Bài toán cần một chiến lược để chọn “tập con tối ưu”.

Ý tưởng greedy: luôn chọn cuộc họp kết thúc sớm nhất

Một chiến lược đơn giản nhưng cực mạnh cho bài toán này:

1. Sắp xếp các cuộc họp theo thời gian kết thúc tăng dần (cuộc nào kết thúc sớm đứng trước).
2. Duyệt theo thứ tự đó:
   • Luôn chọn cuộc họp kế tiếp có thời gian bắt đầu không sớm hơn thời gian kết thúc của cuộc họp vừa chọn.
   • Bỏ qua những cuộc họp bị trùng thời gian với các cuộc đã chọn.

Trực giác: nếu ta chọn cuộc họp kết thúc sớm nhất có thể, ta “giải phóng” phòng họp sớm hơn cho những cuộc họp sau, từ đó tối đa hóa số lượng cuộc họp có thể tham gia.

Vì sao greedy kết thúc sớm nhất là tối ưu?

Có nhiều cách chứng minh, nhưng trực giác như sau:

• Giả sử có một nghiệm tối ưu khác không dùng cuộc họp kết thúc sớm nhất mà dùng một cuộc họp kết thúc muộn hơn.
• Ta có thể “thay thế” cuộc họp kết thúc muộn bằng cuộc họp kết thúc sớm mà không làm giảm số lượng cuộc họp trong lịch.
• Lặp lại lập luận này, cuối cùng ta có một nghiệm tối ưu vẫn theo chiến lược “kết thúc sớm nhất”.

Do đó, chiến lược greedy: sắp xếp theo thời gian kết thúc, rồi chọn tuần tự sẽ cho nghiệm tối ưu.

Mô hình demo: chọn tối đa cuộc họp trên trục thời gian

Để trực quan, ta dùng một trục thời gian đơn giản:

• Mỗi cuộc họp là một đoạn (interval) ngang với nhãn A, B, C, D…
• Bấm nút “Chạy thuật toán”:
  • Các cuộc họp được sắp xếp tăng dần theo thời gian kết thúc.
  • Thuật toán lần lượt chọn các cuộc họp không trùng nhau.
  • Cuộc họp được chọn sẽ tô màu xanh lá.
  • Cuộc họp bị bỏ qua tô màu xám nhạt.
• Khu vực log sẽ hiển thị từng bước thuật toán.

Demo thuật toán Interval Scheduling bằng JavaScript

Giải thích ngắn gọn đoạn code Interval Scheduling

1. Mô tả dữ liệu các cuộc họp

Trong demo, mỗi cuộc họp là một object với id, start, end:

var intervals = [
    { id: "A", start: 1, end: 4 },
    { id: "B", start: 3, end: 5 },
    { id: "C", start: 0, end: 6 },
    { id: "D", start: 5, end: 7 },
    { id: "E", start: 3, end: 9 },
    { id: "F", start: 5, end: 9 },
    { id: "G", start: 6, end: 10 },
    { id: "H", start: 8, end: 10 }
];

Các giá trị start và end được vẽ trên trục [0, 10]. Mỗi cuộc họp sẽ hiển thị như một đoạn ngang có nhãn là id.

2. Thuật toán greedy: sắp xếp theo thời gian kết thúc

Hàm lựa chọn các cuộc họp không trùng nhau:

function selectMaxNonOverlapping(intervals) {
    var sorted = intervals.slice().sort(function(a, b) {
        return a.end - b.end; // sắp xếp theo thời gian kết thúc
    });

    var result = [];
    var currentEnd = -Infinity;

    for (var i = 0; i < sorted.length; i++) {
        var meeting = sorted[i];
        if (meeting.start >= currentEnd) {
            result.push(meeting);
            currentEnd = meeting.end;
        }
    }
    return { selected: result, sorted: sorted };
}

Ý tưởng:

• Sắp xếp các cuộc họp theo end tăng dần.
• Luôn chọn cuộc họp tiếp theo có start ≥ thời gian kết thúc currentEnd của cuộc họp đã chọn gần nhất.

3. Hiển thị kết quả lên giao diện

Mỗi cuộc họp được vẽ bằng một <div> với vị trí và độ rộng tương ứng với start và end. Khi chạy thuật toán:

• Các cuộc họp được chọn sẽ gán class interval-item--selected (màu xanh lá).
• Các cuộc họp bị bỏ qua do chồng chéo với cuộc họp đã chọn sẽ gán class interval-item--skipped (màu xám nhạt).

function applySelection(selected, sorted) {
    var selectedIds = selected.map(function(m) { return m.id; });
    sorted.forEach(function(m) {
        var bar = barMap[m.id];
        bar.classList.remove("interval-item--selected");
        bar.classList.remove("interval-item--skipped");
        if (selectedIds.indexOf(m.id) !== -1) {
            bar.classList.add("interval-item--selected");
        } else {
            bar.classList.add("interval-item--skipped");
        }
    });
}

Kết quả cuối cùng hiển thị:

• Số lượng cuộc họp được chọn.
• Danh sách id các cuộc họp (vd: A, D, H…).
• Log các bước thuật toán từ trái sang phải theo thứ tự thời gian kết thúc.

Khi nào nên dùng thuật toán Interval Scheduling?

• Khi cần sắp xếp lịch họp, lịch sử dụng phòng, lịch máy móc chia sẻ tài nguyên.
• Khi giải bài toán “chọn nhiều interval nhất không giao nhau” trong lập lịch công việc.
• Khi làm việc với các slot thời gian trong hệ thống booking, reservation, ticketing.

Từ đoạn code trên, bạn có thể:

• Mở rộng thêm trường dữ liệu (tên cuộc họp, người tham gia, ưu tiên…).
• Thử nghiệm các bộ dữ liệu khác nhau để hiểu rõ hành vi của thuật toán.
• Kết hợp với UI thực tế (lịch ngày/tuần) để xây dựng hệ thống gợi ý lịch thông minh.