Trong hệ thống xử lý nhật ký hệ thống (Log Processing), làm thế nào để áp dụng chiến lược Greedy trong bài toán Gộp Khoảng Thời Gian Nhật Ký (Merge Intervals) nhằm tối ưu hóa việc gom nhóm các khoảng thời gian log bị trùng lặp thành các phân đoạn độc lập?

Question

Accepted Answer

Bản chất bài toán
Các tiến trình ghi log hệ thống thường tạo ra các khoảng thời gian hoạt động bị chồng chéo lên nhau. Để hiển thị trên Dashboard giám sát, ta cần gộp các khoảng thời gian chồng chéo này lại thành các khoảng thời gian liên tục lớn nhất có thể.
Chiến lược Greedy
Sắp xếp các khoảng thời gian theo thời gian bắt đầu tăng dần, sau đó sử dụng thuật toán tham lam để duyệt và mở rộng khoảng thời gian hiện tại hoặc tạo khoảng thời gian mới nếu không có giao cắt.
Các bước thực hiện

Sắp xếp mảng các khoảng thời gian [start, end] dựa trên giá trị start tăng dần.
Sử dụng một cấu trúc dữ liệu mảng kết quả, đưa khoảng thời gian đầu tiên vào.
Duyệt qua từng khoảng thời gian tiếp theo, so sánh thời điểm start của nó với thời điểm end của khoảng thời gian cuối cùng trong mảng kết quả.
Nếu có sự chồng chéo (start <= last_end), tiến hành cập nhật end của khoảng thời gian trong mảng kết quả bằng giá trị lớn hơn giữa hai end.
Nếu không chồng chéo, thêm khoảng thời gian hiện tại vào mảng kết quả.

Ví dụ mã nguồn minh họa (JavaScript)
function mergeLogIntervals(intervals) {
  if (!intervals || intervals.length <= 1) return intervals;

// Sắp xếp theo thời gian bắt đầu tăng dần
  intervals.sort((a, b) => a[0] - b[0]);

const merged = [intervals[0]];

for (let i = 1; i < intervals.length; i++) {
    const currentInterval = intervals[i];
    const lastMergedInterval = merged[merged.length - 1];

if (currentInterval[0] <= lastMergedInterval[1]) {
      // Gộp khoảng thời gian chồng chéo
      lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
    } else {
      // Thêm mới nếu không chồng chéo
      merged.push(currentInterval);
    }
  }

return merged;
}
Lưu ý thực chiến
Bài toán này rất phổ biến khi Junior làm việc với các hệ thống truy vấn cơ sở dữ liệu hoặc phân tích khoảng thời gian (Time-series Database). Việc quên sắp xếp mảng theo thời gian bắt đầu trước khi áp dụng logic Greedy sẽ khiến thuật toán cho ra kết quả sai lệch hoàn toàn.

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ủ đề