Thuật toán Merge Intervals (Gộp khoảng thời gian) là một kỹ thuật quan trọng trong lập trình, thường được sử dụng trong các bài toán liên quan đến thời gian biểu, lịch trình hoặc vùng giao nhau của các đoạn số. Trong bài viết này, chúng ta sẽ cùng tìm hiểu về thuật toán này, cách triển khai và ứng dụng thực tế.
1. Bài toán Merge Intervals
Cho một danh sách các khoảng thời gian (hoặc đoạn số) được biểu diễn dưới dạng các cặp ( (start, end) ), nhiệm vụ của chúng ta là gộp các khoảng thời gian chồng chéo nhau thành các khoảng liên tục.
Ví dụ:
Input:
[[1, 3], [2, 6], [8, 10], [15, 18]]
Output:
[[1, 6], [8, 10], [15, 18]]
Giải thích: Khoảng ([1,3]) và ([2,6]) có giao 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, ta luôn gặp các khoảng thời gian theo thứ tự thời gian.
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 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, thêm khoảng mới vào danh sách kết quả.
3. Triển khai thuật toán Merge Intervals bằng Python
Dưới đây là đoạn code minh họa thuật toán Merge Intervals:
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 code:
- 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.
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 Merge Intervals
- Lịch trình phòng họp: Hợp nhất các khoảng thời gian đặt phòng trùng lặp.
- Quản lý sự kiện: Gộp các khoảng thời gian làm việc của nhân viên để tối ưu 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 Merge Intervals là một kỹ thuật quan trọng trong lập trình, đặc biệt hữu ích khi làm việc với dữ liệu thời gian và khoảng liên tục. Hy vọ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ế!