Giới thiệu Thuật Toán Gộp Khoảng Thời Gian (Merge Intervals)

Thuật toán Gộp Khoảng Thời Gian (Merge Intervals) là một trong những kỹ thuật quan trọng trong lập trình. Kỹ thuật này thường được áp dụng trong các bài toán liên quan đến lịch trình thời gian, công việc, hoặc các đoạn số có sự giao nhau. Trong bài viết này, chúng ta sẽ cùng nhau khám phá sâu hơn về thuật toán này, từ cách triển khai cho đến các ứng dụng thực tiễn.

1. Bài Toán Gộp Khoảng Thời Gian

Được cho một danh sách các khoảng thời gian (hoặc đoạn số) dưới dạng các cặp (start, end), nhiệm vụ của chúng ta là gộp những khoảng thời gian chồng chéo thành các khoảng liên tục.

Ví Dụ:

Input:

Copy

[[1, 3], [2, 6], [8, 10], [15, 18]]

Output:

Copy

[[1, 6], [8, 10], [15, 18]]

Giải thích: Khoảng ([1, 3]) và ([2, 6]) chồng chéo nhau nên được gộp lại thành ([1, 6]).

2. Cách Tiếp Cận Giải Quyết Bài Toán

Bước 1: Sắp Xếp Các Khoảng Theo Giá Trị Bắt Đầu (Start)

Điều này giúp đảm bảo rằng khi duyệt qua danh sách, chúng ta sẽ luôn xét đến các khoảng thời gian theo thứ tự trước sau.

Bước 2: Duyệt Danh Sách Và Hợp Nhất Các Khoảng

Duyệt từng khoảng và kiểm tra xem nó có giao nhau với khoảng trước đó không.
Nếu có giao nhau, cập nhật điểm kết thúc (end) của khoảng gộp.
Nếu không có giao nhau, thêm khoảng mới vào danh sách kết quả.

3. Triển Khai Thuật Toán Gộp Khoảng Thời Gian Bằng Python

Dưới đây là đoạn mã minh họa cho thuật toán Gộp Khoảng Thời Gian:

python Copy

from typing import List

def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []
    
    # Sắp xếp danh sách theo thời gian bắt đầu
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last_merged = merged[-1]
        
        if current[0] <= last_merged[1]:  # Có giao nhau
            last_merged[1] = max(last_merged[1], current[1])
        else:
            merged.append(current)
    
    return merged

# Kiểm tra với ví dụ
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge_intervals(intervals))

Giải Thích Mã Nguồn:

Sắp xếp danh sách theo giá trị bắt đầu (start).
Duyệt qua từng khoảng trong danh sách:
- Nếu khoảng hiện tại giao nhau với khoảng trước, cập nhật điểm kết thúc.
- Nếu không, thêm vào danh sách kết quả.
Trả về danh sách các khoảng sau khi đã gộp lại.

4. Độ Phức Tạp Của Thuật Toán

Bước Sắp Xếp: O(n log n)
Bước Duyệt Danh Sách: O(n)
Tổng Độ Phức Tạp: O(n log n), do bước sắp xếp chiếm nhiều thời gian nhất.

5. Ứng Dụng Thực Tế Của Thuật Toán Gộp Khoảng Thời Gian

Lịch Trình Phòng Họp: Hợp nhất các khoảng thời gian đặt phòng trùng nhau.
Quản Lý Sự Kiện: Gộp khoảng thời gian làm việc của nhân viên nhằm tối ưu hóa lịch trình.
Xử Lý Dữ Liệu Logs: Gộp các khoảng thời gian xảy ra lỗi hệ thống để đơn giản hóa báo cáo.

6. Kết Luận

Thuật toán Gộp Khoảng Thời Gian là một công cụ mạnh mẽ trong lập trình, đặc biệt hữu ích khi chúng ta làm việc với dữ liệu về thời gian và các khoảng liên tục. Hy vọng rằng bài viết này đã giúp bạn hiểu rõ hơn về thuật toán và cách triển khai nó trong thực tế!
source: viblo

Hướng Dẫn Chi Tiết Về Thuật Toán Gộp Khoảng Thời Gian (Merge Intervals)