Trong hệ thống giám sát an ninh mạng SIEM, làm thế nào để áp dụng chiến lược Greedy trong bài toán phủ khoảng thời gian nhật ký (Interval Partitioning / Minimum Platforms) để xác định số lượng luồng xử lý luân phiên tối thiểu cần cấp phát cho các tiến trình quét log?

Question

Accepted Answer

Để quản lý tài nguyên xử lý luồng log trong hệ thống SIEM mà không gây quá tải CPU, bài toán Interval Partitioning giúp tính toán số lượng luồng đồng thời tối thiểu cần thiết dựa trên các khoảng thời gian bắt đầu và kết thúc của các gói log.
Bản chất cơ chế hoạt động

Tách riêng mảng thời gian bắt đầu (Start Times) và mảng thời gian kết thúc (End Times) của tất cả các tiến trình quét log.
Sắp xếp độc lập cả hai mảng theo thứ tự tăng dần.
Sử dụng hai con trỏ (Two Pointers) để duyệt qua các mảng: nếu thời gian bắt đầu nhỏ hơn hoặc bằng thời gian kết thúc, nghĩa là có thêm một tiến trình chồng chéo và cần tăng số lượng luồng lên một đơn vị; ngược lại, nếu thời gian bắt đầu lớn hơn, một tiến trình đã hoàn thành và chúng ta giảm số lượng luồng hoạt động.
Ghi nhận giá trị lớn nhất của số lượng luồng trong suốt quá trình duyệt, đó chính là số lượng luồng tối thiểu cần cấp phát.

Ví dụ cài đặt bằng Python cho cấp độ Junior
def min_processing_threads(intervals):
    if not intervals:
        return 0

start_times = sorted([i[0] for i in intervals])
    end_times = sorted([i[1] for i in intervals])

n = len(intervals)
    i = 0
    j = 0
    current_threads = 0
    max_threads = 0

while i < n:
        if start_times[i] <= end_times[j]:
            current_threads += 1
            max_threads = max(max_threads, current_threads)
            i += 1
        else:
            current_threads -= 1
            j += 1

return max_threads

# Kiểm thử
logs = [(1, 5), (2, 6), (4, 8), (7, 9)]
print(min_processing_threads(logs))
# Kết quả: 3
Lưu ý kinh nghiệm thực chiến

Độ phức tạp thời gian là O(N log N) do thao tác sắp xếp hai mảng thời gian.
Kỹ thuật này giúp kỹ sư hệ thống dự báo chính xác nhu cầu scale-up cụm hạ tầng xử lý dữ liệu lớn (Big Data pipeline) trước các sự kiện cao điểm.

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