Cấu trúc dữ liệu và Giải thuật Bài 20: Bài toán kinh điển: Hợp nhất các khoảng trùng lặp (Merge Intervals).

Trong các hệ thống phần mềm, chúng ta thường xuyên phải làm việc với dữ liệu có tính chất "khoảng" (được xác định bởi điểm bắt đầu và điểm kết thúc). Ví dụ: Một hệ thống đặt phòng họp (từ 9h00 đến 10h30), một lịch trình chạy tàu của Metro Line 1, hoặc phân bổ các dải địa chỉ IP.

Khi có hàng ngàn lịch trình được đẩy vào hệ thống một cách lộn xộn, làm sao bạn biết được tổng thời gian thực tế mà phòng họp bị chiếm dụng, hoặc có bao nhiêu chuyến tàu đang bị trùng giờ nhau? Đó là lúc bài toán Merge Intervals (Hợp nhất các khoảng trùng lặp) trở thành một bài kiểm tra năng lực thiết kế logic kinh điển.

1. Bản chất của sự chồng chéo (Overlapping)

Một khoảng (Interval) được biểu diễn bằng một mảng hoặc cấu trúc gồm hai phần tử: [start, end].

Cho hai khoảng A và B (giả sử A bắt đầu trước, tức là A.start <= B.start).

Chúng ta nói B bị "chồng chéo" lên A khi và chỉ khi: Điểm bắt đầu của B nằm trước hoặc bằng điểm kết thúc của A.

Nói cách logic: B.start <= A.end.

Ví dụ:

• Khoảng A: [1, 5] và Khoảng B: [2, 6]. Vì 2 <= 5, hai khoảng này giao nhau. Kết quả hợp nhất sẽ trải dài từ điểm bắt đầu sớm nhất đến điểm kết thúc muộn nhất: [1, 6].

• Khoảng A: [1, 5] và Khoảng C: [6, 8]. Vì 6 > 5, chúng không liên quan đến nhau.

2. Giải pháp ngây thơ (Brute Force) và sự hỗn loạn

Nếu nhận được một danh sách các khoảng lộn xộn: [[8, 10], [1, 3], [2, 6], [15, 18]].

Cách làm theo bản năng là lấy khoảng đầu tiên [8, 10] đi so sánh với tất cả các khoảng còn lại xem có trùng không. Nếu có thì gộp lại, rồi lại lấy khoảng mới đi so sánh tiếp.

Cách làm này sẽ vấp phải một vấn đề lớn: Bạn phải liên tục quét đi quét lại mảng dữ liệu. Độ phức tạp thời gian sẽ bùng nổ lên mức $O(n^2)$. Trên một hệ thống lịch trình có hàng triệu sự kiện, cách này hoàn toàn không khả thi.

3. Tối ưu hóa: Sức mạnh của việc Sắp xếp (Sorting)

Bạn không thể tìm thấy sự ngăn nắp trong một mớ hỗn độn. Thay vì cố gắng gộp các khoảng lộn xộn, bước đột phá của thuật toán này là Sắp xếp tất cả các khoảng theo thời gian bắt đầu (start) từ nhỏ đến lớn.

Khi danh sách đã được sắp xếp, một tính chất tuyệt vời xuất hiện: Bất kỳ khoảng nào có khả năng trùng lặp với nhau đều chắc chắn sẽ nằm sát cạnh nhau. Bạn không bao giờ phải nhìn lại phía sau nữa.

Các bước thực thi:

1. Sắp xếp: Chi phí thời gian $O(n \log n)$. Kết quả: [[1, 3], [2, 6], [8, 10], [15, 18]].

2. Khởi tạo mảng kết quả: Đưa khoảng đầu tiên [1, 3] vào mảng kết quả. Nó đang là khoảng "hiện tại" (Current Interval) mà ta xem xét.

3. Duyệt mảng một chiều (Linear Scan):

   • Đọc khoảng tiếp theo [2, 6]. Kiểm tra xem nó có trùng với khoảng hiện tại [1, 3] không? Có, vì 2 <= 3.

   • Hợp nhất chúng bằng cách cập nhật điểm kết thúc của khoảng hiện tại thành giá trị lớn nhất giữa hai điểm kết thúc: MAX(3, 6) = 6. Khoảng hiện tại trở thành [1, 6].

   • Đọc tiếp [8, 10]. Nó có trùng với [1, 6] không? Không, vì 8 > 6. Lúc này khoảng [1, 6] đã hoàn thiện, ta giữ nguyên nó trong mảng kết quả, và chọn [8, 10] làm khoảng hiện tại mới để tiếp tục duyệt.

Toàn bộ quá trình quét chỉ đi qua mảng đúng 1 lần, mất $O(n)$ thời gian. Tổng thời gian của toàn thuật toán bị chi phối bởi bước sắp xếp: $O(n \log n)$.

4. Triển khai thuật toán bằng Golang

Golang cung cấp gói sort tích hợp cực kỳ mạnh mẽ để chúng ta sắp xếp mảng 2 chiều theo tiêu chí tùy chỉnh (ở đây là chỉ số phần tử thứ 0).

Go

import (
    "sort"
)

func mergeIntervals(intervals [][]int) [][]int {
    if len(intervals) <= 1 {
        return intervals
    }

    // 1. Sắp xếp các khoảng theo điểm bắt đầu (start time)
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    var result [][]int
    // 2. Lấy khoảng đầu tiên làm mốc khởi điểm
    currentInterval := intervals[0]
    result = append(result, currentInterval)

    for i := 1; i < len(intervals); i++ {
        nextInterval := intervals[i]
        
        // Lấy con trỏ đến phần tử cuối cùng trong mảng result để dễ thao tác
        lastMerged := result[len(result)-1]

        // 3. Kiểm tra chồng chéo
        if nextInterval[0] <= lastMerged[1] {
            // Hợp nhất: Chọn điểm kết thúc muộn hơn
            if nextInterval[1] > lastMerged[1] {
                lastMerged[1] = nextInterval[1]
            }
        } else {
            // Không chồng chéo: Đẩy khoảng mới vào kết quả
            result = append(result, nextInterval)
        }
    }

    return result
}

5. Ứng dụng mở rộng của bài toán

Tư duy hợp nhất các khoảng không chỉ dừng lại ở bài tập LeetCode. Nó là lõi thuật toán cho hàng loạt các module hệ thống thực tế:

• Tối ưu hóa Database (Vacuum/Compaction): Trong các cơ sở dữ liệu chuỗi thời gian (Time-Series Database như TimescaleDB), dữ liệu cũ thường được lưu dưới dạng các khối (chunks) theo thời gian. Khi hợp nhất các khối dữ liệu rời rạc trùng lặp lại với nhau, hệ thống giải phóng được dung lượng đĩa và tăng tốc độ truy xuất.

• Xử lý đồ họa: Khi render giao diện website, nếu có nhiều hộp thoại (div) đang đè lên nhau, trình duyệt sẽ dùng thuật toán này để hợp nhất các tọa độ vùng hiển thị, giúp GPU chỉ phải vẽ lại một vùng chữ nhật lớn duy nhất thay vì vẽ đè lên nhau nhiều lần.

• Nhận diện tín hiệu: Khi xử lý nhiễu tín hiệu từ các cảm biến điện tử, các khoảng thời gian bị nhiễu sóng (noise spikes) gần nhau có thể được gộp lại thành một dải nhiễu liên tục để bộ lọc phần mềm dễ dàng loại bỏ một lần.

Bài 20 này chính thức khép lại Chương 2. Bạn đã thấu hiểu Mảng từ tầng vật lý của RAM, nắm được giới hạn của sự dịch chuyển bộ nhớ, và bắt đầu làm quen với các thuật toán thao tác trên một mảng (Kadane, Prefix Sum, Merge Intervals).

Từ Chương 3, chúng ta sẽ bắt đầu chuyển sang một cảnh giới mới của việc giải quyết vấn đề: Thay vì dùng 1 vòng lặp để đi từ đầu đến cuối, chúng ta sẽ thả nhiều con trỏ chạy song song trên cùng một mảng để ép thời gian xử lý xuống mức thấp nhất.