Thuật toán Line Sweep là gì? Giải thích dễ hiểu kèm demo đếm số khoảng thời gian trùng nhiều nhất

Thuật toán Line Sweep là gì? Giải thích dễ hiểu kèm demo đếm số khoảng thời gian trùng nhiều nhất

Trong rất nhiều bài toán thực tế, ta có một loạt các khoảng thời gian (events, cuộc họp, đoạn chiếu quảng cáo, phiên truy cập…) và muốn biết những thông tin như: tại thời điểm nào có nhiều sự kiện diễn ra nhất?, hoặc có khoảng thời gian nào bị quá tải không?. Nếu duyệt từng thời điểm hoặc so sánh từng cặp khoảng một cách ngây thơ thì sẽ rất tốn thời gian. Lúc này, Line Sweep Algorithm (thuật toán quét đường thẳng) là một kỹ thuật kinh điển trong hình học tính toán và xử lý intervals, giúp giải quyết những bài toán dạng này một cách hiệu quả.

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

• Hiểu trực giác của thuật toán Line Sweep trên trục thời gian 1 chiều.
• Áp dụng để đếm số lượng khoảng thời gian trùng tại mỗi thời điểm.
• Tìm ra số lượng trùng tối đa và những khoảng thời gian đạt giá trị đó.
• Xem demo trực quan bằng JavaScript với log từng bước.

Line Sweep là gì?

Ý tưởng của Line Sweep rất đơn giản: thay vì xử lý cả “khối” dữ liệu cùng lúc, ta tưởng tượng có một đường thẳng (hoặc một điểm) quét qua không gian (ở đây là trục thời gian) từ trái sang phải. Mỗi khi đường quét đi qua:

• “Gặp” một điểm bắt đầu của khoảng → ta tăng số lượng sự kiện đang hoạt động.
• “Gặp” một điểm kết thúc của khoảng → ta giảm số lượng sự kiện đang hoạt động.

Bằng cách:

1. Biến mỗi khoảng [start, end) thành hai “sự kiện” trên trục thời gian:
   • (time = start, delta = +1): bắt đầu một sự kiện.
   • (time = end, delta = -1): kết thúc một sự kiện.
2. Sắp xếp tất cả các sự kiện này theo thời gian tăng dần (nếu trùng thì xử lý -1 trước +1 để không đếm trùng tại điểm biên).
3. Duyệt tuần tự:
   • Cộng dồn delta để biết hiện tại có bao nhiêu khoảng đang “mở”.
   • Cập nhật giá trị max nếu số đang mở vượt qua kỷ lục trước đó.

Kết quả: ta vừa biết được số lượng khoảng trùng tối đa, vừa có thể xác định được khoảng thời gian mà con số đó đạt được.

Ví dụ trực giác trên trục thời gian

Giả sử ta có 5 khoảng (ví dụ các cuộc họp):

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

Nếu vẽ trên trục thời gian, ta có thể nhìn bằng mắt để đoán khoảng từ 3 đến 4 có khá nhiều cuộc họp chồng lên nhau. Line Sweep sẽ:

• Tạo sự kiện:
  • A: (1, +1), (4, -1)
  • B: (2, +1), (6, -1)
  • C: (5, +1), (8, -1)
  • D: (3, +1), (5, -1)
  • E: (7, +1), (9, -1)
• Sắp xếp theo thời gian và lần lượt cộng dồn để biết ở mỗi đoạn có bao nhiêu khoảng đang “sống”.

Ta sẽ tìm ra:

• Số lượng khoảng trùng nhiều nhất (max overlap).
• Các đoạn thời gian mà số lượng đang hoạt động đạt max này.

Mô hình demo: đếm số khoảng thời gian trùng nhiều nhất

Trong demo dưới đây:

• Mỗi dòng là một “cuộc họp” trên trục thời gian từ 0 đến 10.
• Mỗi cuộc họp là một đoạn ngang màu xám có nhãn A, B, C, D, E.
• Nhấn “Chạy Line Sweep”:
  • Thuật toán sẽ dựng danh sách sự kiện (start/end) và sắp xếp theo thời gian.
  • Từng bước cập nhật số lượng khoảng đang mở.
  • Tìm ra giá trị trùng tối đa và các đoạn thời gian tương ứng.
• Khu vực log sẽ hiển thị chi tiết từng sự kiện và cách cập nhật biến.

Demo Line Sweep Algorithm bằng JavaScript

Giải thích ngắn gọn đoạn code Line Sweep

1. Mô tả dữ liệu các khoảng

Trong demo, mỗi khoảng được mô tả bằng id, start, end:

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

Ta vẽ các khoảng này trên trục [0, 10] trong phần timeline và đồng thời dùng chúng làm input cho thuật toán.

2. Xây dựng danh sách “sự kiện” start/end

Mỗi khoảng [start, end) được biến thành hai event:

• (time = start, delta = +1, type = "start")
• (time = end, delta = -1, type = "end")

Đoạn code tạo và sắp xếp các event:

function buildEvents(intervals) {
    var events = [];
    intervals.forEach(function(it) {
        events.push({ time: it.start, delta: +1, id: it.id, type: "start" });
        events.push({ time: it.end,   delta: -1, id: it.id, type: "end" });
    });

    events.sort(function(a, b) {
        if (a.time !== b.time) {
            return a.time - b.time;
        }
        return a.delta - b.delta; // end (-1) trước start (+1) nếu trùng time
    });

    return events;
}

3. Duyệt Line Sweep và tìm trùng tối đa

Khi đã có danh sách event đã sắp xếp, ta duyệt từ trái sang phải:

• currentActive: số khoảng đang hoạt động tại thời điểm hiện tại.
• maxActive: giá trị lớn nhất của currentActive từng thấy.
• maxSegments: danh sách các đoạn thời gian mà currentActive = maxActive.

Đoạn code chính:

function sweep(intervals, log) {
    var events = buildEvents(intervals);
    var currentActive = 0;
    var maxActive = 0;
    var segments = [];

    for (var i = 0; i < events.length; i++) {
        var e = events[i];
        var nextTime = (i + 1 < events.length) ? events[i + 1].time : null;

        log(
            "Tại thời điểm " + e.time +
            ", gặp event " + e.type.toUpperCase() +
            " của " + e.id + " (delta = " + e.delta + ")."
        );

        currentActive += e.delta;
        log("→ Số khoảng đang hoạt động = " + currentActive + ".");

        if (nextTime !== null && nextTime > e.time) {
            if (currentActive > maxActive) {
                maxActive = currentActive;
                segments = [];
                if (currentActive > 0) {
                    segments.push({ start: e.time, end: nextTime });
                }
            } else if (currentActive === maxActive && currentActive > 0) {
                segments.push({ start: e.time, end: nextTime });
            }
        }
    }

    return {
        maxActive: maxActive,
        segments: segments,
        events: events
    };
}

Ý tưởng:

• Sau mỗi event, ta biết số khoảng đang mở ở đoạn [time, nextTime).
• Nếu currentActive lớn hơn maxActive → cập nhật max và reset danh sách đoạn.
• Nếu bằng maxActive → thêm đoạn tương ứng vào danh sách.

4. Hiển thị kết quả ra giao diện

Sau khi chạy sweep, ta dùng:

• maxActive để hiển thị “Số khoảng trùng tối đa”.
• segments để liệt kê các đoạn thời gian tương ứng, ví dụ: [3, 4), [4, 5)…

Trong demo, kết quả được in ra khu vực #ls-result và chi tiết từng event được log trong #ls-log.

Khi nào nên dùng Line Sweep?

• Khi làm việc với nhiều khoảng thời gian và muốn:
  • Đếm số lượng trùng tại mọi thời điểm.
  • Tìm giá trị trùng tối đa.
  • Phân tích vùng quá tải (overload) trên timeline.
• Khi giải các bài toán interval trên trục số 1 chiều mà giải pháp naïve O(n²) là quá chậm.
• Khi cần nền tảng cho các bài toán hình học và thời gian phức tạp hơn (rectangle union, phát hiện giao nhau đoạn thẳng, v.v.).

Từ demo JavaScript trên, bạn có thể mở rộng:

• Cho phép người dùng tự nhập thêm khoảng thời gian mới.
• Tô màu đậm các khoảng tham gia vào đoạn có trùng tối đa.
• Mở rộng sang bài toán hai chiều (Line Sweep cho hình chữ nhật trên mặt phẳng).