Gộp Cuộc Họp Liên Tục VPBank

Mô tả

Chị Lan quản lý lịch họp cho một nhóm chuyên viên tại VPBank. Mỗi ngày chị nhận về danh sách các cuộc họp, mỗi cuộc ghi rõ thời điểm bắt đầu và thời điểm kết thúc (tính theo phút từ đầu ngày). Hai cuộc họp được xem là dính liền nếu khoảng thời gian của chúng có giao nhau hoặc chạm nhau ở đầu mút — nghĩa là cuộc sau bắt đầu không sau lúc cuộc trước kết thúc.

Nhiệm vụ của bạn là gộp tất cả các cuộc họp giao nhau hoặc chạm nhau lại thành các "khung bận" liên tục. Mỗi khung bận là khoảng thời gian dài nhất mà trong đó mọi cuộc họp đều nối tiếp nhau không ngắt. Sau khi gộp xong, chị Lan sẽ nhìn vào danh sách khung bận để quyết định xem có thể chèn thêm một cuộc họp mới hay không.

Đầu vào

• Một mảng meetings, mỗi phần tử là một cặp [start, end] (số nguyên, start < end).
• n là số lượng cuộc họp, 1 ≤ n ≤ 10^5.
• 0 ≤ start < end ≤ 10^9.

Đầu ra

• Trả về một mảng các khung bận đã gộp, mỗi phần tử là [mergedStart, mergedEnd], sắp xếp theo thứ tự thời gian tăng dần.

Ràng buộc

• 1 ≤ n ≤ 10^5.
• 0 ≤ start, end ≤ 10^9, luôn đảm bảo start < end cho mọi cuộc họp.
• Độ phức tạp thời gian mục tiêu: O(n log n).

Ví dụ

Ví dụ 1:

Đầu vào: [[1, 3], [2, 6], [8, 10], [15, 18]]

Giải thích từng bước:

• Sắp xếp theo thời điểm bắt đầu: đã sẵn sàng.
• Cuộc [1, 3] và giao nhau (2 ≤ 3) → gộp thành .