Phỏng vấn

Gộp các khoảng thời gian (Merge Intervals) và bài toán phòng họp

Các bài toán khoảng thời gian (Interval Problems) như gộp lịch bận, chèn cuộc họp mới hay tính số phòng họp tối thiểu đều khởi đầu bằng một thao tác quyết định: sắp xếp các đoạn theo mốc bắt đầu. Khi các mốc trái đã tăng dần, mọi quan hệ chồng lấp phức tạp đều rút gọn về phép so sánh với đúng đoạn cuối cùng đang giữ.

Nhận diện nhóm bài khoảng thời gian và câu hỏi làm rõ quy ước biên

Trong thực tế phát triển hệ thống đặt lịch, quản lý tài nguyên máy chủ hay xử lý chuỗi sự kiện theo thời gian, dữ liệu đầu vào thường được cho dưới dạng danh sách các cặp [start, end]. Trong phỏng vấn thuật toán, nhóm bài này xoay quanh bốn câu hỏi cốt lõi:

  1. Merge Intervals: Gộp tất cả các khoảng chồng lấp thành danh sách các khoảng rời nhau gọn nhất.
  2. Insert Interval: Chèn một khoảng mới vào danh sách các khoảng đã sắp xếp và không chồng lấp.
  3. Meeting Rooms I & II: Kiểm tra một người có thể tham dự hết các cuộc họp không, hoặc tìm số phòng họp tối thiểu cần mở để phục vụ toàn bộ lịch họp.
  4. Non-overlapping Intervals / Minimum Arrows to Burst Balloons: Tìm số khoảng cần xóa ít nhất để phần còn lại không chồng lấp (hoặc chọn tập khoảng rời nhau lớn nhất).

Trước khi bắt tay vào giải, bạn hãy hỏi người phỏng vấn ba điểm cực kỳ quan trọng về quy ước biên:

  • Hai khoảng chạm nhau tại đúng một điểm có tính là chồng lấp không? Trong bài Merge Intervals, hai đoạn [1, 4] và [4, 5] thường được quy ước là chạm nhau và phải gộp thành [1, 5] (điều kiện chồng lấp là next.start <= cur.end, tức không tách rời next.start > cur.end). Nhưng trong bài Meeting Rooms II, một cuộc họp kết thúc lúc 10 giờ ([5, 10]) và cuộc họp kế tiếp bắt đầu lúc 10 giờ ([10, 15]) lại không xung đột — khách hàng trước vừa trả phòng thì đoàn sau vào dùng ngay được (điều kiện tái sử dụng phòng là earliest_end <= next.start). Chỉ lệch dấu < hay > so với <= hay >= ở điểm chạm này là kết quả đã khác hẳn.
  • Đầu vào đã được sắp xếp chưa và có đảm bảo start <= end (không có đoạn ngược start > end) không? Đừng bao giờ giả định các khoảng trong input đã tăng dần theo start, trừ khi đề bài nói rõ như ở bài Insert Interval.
  • Giá trị mốc thời gian có thể lớn tới mức nào? Nếu tọa độ lên tới 10^9 hoặc là timestamp 64-bit, bạn không thể tạo mảng đánh dấu theo từng giây mà bắt buộc phải sắp xếp các mốc đầu mút (O(n log n)).
Ý chính

Khi các khoảng đã được sắp xếp tăng dần theo mốc bắt đầu l_1 <= l_2 <= ... <= l_n, mọi khoảng chồng lấp sẽ nằm gom lại thành các cụm liên tiếp. Lúc duyệt tới khoảng [l, r], ta chỉ cần so sánh l với mốc kết thúc last_r của khoảng vừa gộp gần nhất: nếu l <= last_r thì nối rộng last_r = max(last_r, r), ngược lại khi l > last_r thì mở một khoảng độc lập mới.

Lịch họp [0, 30], [5, 10], [15, 20]: Gộp khoảng vs Đếm phòng t = 0 5 10 15 20 30 Phòng #1: Cuộc họp [0, 30] (bận xuyên suốt từ 0 đến 30) [5, 10] [15, 20] ← Chung Phòng #2 Merge Intervals Hợp thành 1 đoạn: [0, 30] Meeting Rooms II 15 >= 10: cần đúng 2 phòng
Lịch họp: [0, 30], [5, 10], [15, 20] So sánh Gộp đoạn và Đếm phòng họp Phòng #1: Họp [0, 30] Phòng #2: [5, 10] Phòng #2: [15, 20] Merge Intervals Gộp cả 3 thành 1 đoạn [0, 30] Meeting Rooms II 15 >= 10: tái sử dụng → cần 2 phòng
Hình 1. So sánh hai bài toán trên cùng bộ lịch họp [0, 30], [5, 10], [15, 20]: Merge Intervals gộp cả 3 thành một đoạn [0, 30], trong khi Meeting Rooms II cần đúng 2 phòng vì cuộc họp [15, 20] tái sử dụng được phòng của [5, 10].

Bất biến sắp xếp theo mốc bắt đầu: Vì sao chỉ cần nhìn đoạn cuối cùng?

Nếu giữ nguyên danh sách lộn xộn ban đầu, để biết một đoạn có giao với đoạn nào khác hay không, ta phải so sánh nó với mọi đoạn còn lại tốn O(n²), thậm chí sau khi gộp hai đoạn lại tạo ra một đoạn lớn hơn có thể quay ngược lại giao với các đoạn đã xét trước đó.

Phép sắp xếp tăng dần theo mốc bắt đầu l giải quyết triệt để rắc rối này. Giả sử danh sách kết quả merged đang có đoạn cuối cùng là [L, R] và ta xét đoạn tiếp theo [l, r]. Vì đã sắp xếp nên chắc chắn \(l \ge L\). Khi đó chỉ có hai khả năng loại trừ nhau:

  • Trường hợp 1 (\(l \le R\)): Vì \(L \le l \le R\), điểm bắt đầu \(l\) của đoạn mới nằm ngay bên trong đoạn [L, R]. Hai đoạn chồng lấp nhau và hợp của chúng là [L, max(R, r)]. Ta phải lấy max(R, r) chứ không gán thẳng bằng r, bởi đoạn trước [0, 30] có thể dài bao trùm hoàn toàn đoạn sau [5, 10].
  • Trường hợp 2 (\(l > R\)): Không chỉ đoạn [l, r] tách rời khỏi [L, R], mà mọi đoạn đứng sau [l, r] đều có mốc bắt đầu \(l' \ge l > R\), nghĩa là không bao giờ có đoạn nào phía sau còn chạm được vào [L, R] nữa! Đoạn [L, R] đã chính thức "đóng sổ" và ta đẩy [l, r] vào cuối danh sách merged làm đoạn đang mở mới.

Phân biệt Merge Intervals và Meeting Rooms II qua bảng chạy tay

Một nhầm lẫn rất hay gặp ở người mới học là tưởng rằng số phòng họp tối thiểu bằng số đoạn sau khi gộp (hoặc bằng tổng số đoạn trừ đi số đoạn gộp). Hình 1 chỉ ra phản ví dụ rõ nét nhất với ba cuộc họp [0, 30], [5, 10] và [15, 20]:

  • Nếu chạy Merge Intervals, cuộc họp dài [0, 30] nuốt trọn cả [5, 10] lẫn [15, 20], nên sau khi gộp chỉ còn đúng 1 khoảng bận liên tục [0, 30].
  • Nhưng nếu xếp Meeting Rooms II, tại thời điểm t = 6, chỉ có hai cuộc họp [0, 30] và [5, 10] diễn ra song song. Tới t = 10, cuộc họp [5, 10] kết thúc và trả lại Phòng #2; đến t = 15, cuộc họp [15, 20] vào ngay Phòng #2 đó. Vì vậy ta chỉ cần 2 phòng họp, chứ không phải 1 phòng hay 3 phòng.

Để giải Meeting Rooms II chuẩn xác, sau khi sắp xếp các cuộc họp tăng dần theo start, ta dùng một Min-Heap lưu thời điểm kết thúc end của các phòng đang có người họp. Đỉnh của Min-Heap (min_heap.top()) luôn cho biết căn phòng nào sẽ trống sớm nhất:

  • Khi cuộc họp mới [l, r] tới, nếu min_heap.top() <= l (tức không còn bận min_heap.top() > l), căn phòng trống sớm nhất đã kết thúc trước hoặc đúng lúc cuộc họp mới bắt đầu. Ta lấy căn phòng đó ra (pop) và cập nhật giờ kết thúc mới r vào (push(r)).
  • Nếu min_heap.top() > l, ngay cả phòng kết thúc sớm nhất cũng vẫn đang bận tại thời điểm l, nên bắt buộc phải mở thêm một phòng mới (push(r) mà không pop).

Hãy chạy tay song song cả hai thuật toán trên danh sách 4 đoạn kinh điển [1, 3], [2, 6], [8, 10], [15, 18]:

Bước Đoạn [l, r] đang xét Danh sách merged (Merge Intervals) Trạng thái min_heap các giờ kết thúc (Meeting Rooms II) Giải thích hành động
1 [1, 3] [[1, 3]] [3] (cỡ 1) Khởi tạo đoạn đầu tiên và mở Phòng #1 kết thúc lúc 3
2 [2, 6] 2 <= 3 → gộp thành [[1, 6]] top = 3 > 2 (chưa trống) → push(6) → [3, 6] (cỡ 2) Hai đoạn giao nhau trên [2, 3]; phải mở thêm Phòng #2 kết thúc lúc 6
3 [8, 10] 8 > 6 → thêm mới [[1, 6], [8, 10]] top = 3 <= 8 → pop(3), push(10) → [6, 10] (cỡ 2) Đoạn mới tách rời [1, 6]; tái sử dụng Phòng #1 (vốn trống từ mốc 3)
4 [15, 18] 15 > 10 → thêm [[1, 6], [8, 10], [15, 18]] top = 6 <= 15 → pop(6), push(18) → [10, 18] (cỡ 2) Tách rời hoàn toàn; tái sử dụng Phòng #2 (trống từ mốc 6)

Kết thúc quá trình, danh sách sau khi gộp có 3 khoảng rời nhau: [1, 6], [8, 10], [15, 18]; còn số lượng phần tử trong min_heap là 2, tương ứng với tối đa 2 phòng họp hoạt động đồng thời.

Code mẫu C++17, Python và Java 21

Chương trình dưới đây đọc n khoảng thời gian, thực hiện đồng thời hai việc: tính số phòng họp tối thiểu bằng Min-Heap và hợp nhất các khoảng chồng lấp. Dòng đầu tiên của kết quả in ra <số đoạn sau khi gộp> <số phòng họp tối thiểu>, tiếp theo là từng đoạn đã gộp theo thứ tự tăng dần.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int min_meeting_rooms(vector<pair<long long, long long>> intervals) {
    if (intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end());
    priority_queue<long long, vector<long long>, greater<long long>> min_heap;
    for (const auto& [l, r] : intervals) {
        if (!min_heap.empty() && min_heap.top() <= l) {
            min_heap.pop();
        }
        min_heap.push(r);
    }
    return (int)min_heap.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<pair<long long, long long>> a(n);
    for (auto& [l, r] : a) {
        cin >> l >> r;
        if (l > r) swap(l, r);
    }
    int rooms = min_meeting_rooms(a);
    sort(a.begin(), a.end());
    vector<pair<long long, long long>> merged;
    for (const auto& [l, r] : a) {
        if (merged.empty() || l > merged.back().second) {
            merged.push_back({l, r});
        } else {
            merged.back().second = max(merged.back().second, r);
        }
    }
    cout << merged.size() << ' ' << rooms << '\n';
    for (const auto& [l, r] : merged) {
        cout << l << ' ' << r << '\n';
    }
    return 0;
}

Độ phức tạp và lưu ý theo từng ngôn ngữ

  • Thời gian: O(n log n).
    • Với Merge Intervals, bước sắp xếp đầu tiên tốn O(n log n), sau đó vòng quét tuyến tính qua n khoảng tốn O(n).
    • Với Meeting Rooms II, ngoài bước sắp xếp O(n log n), mỗi khoảng thực hiện tối đa một lệnh pop và một lệnh push trên Min-Heap có kích thước không vượt quá n, tốn thêm O(n log n).
  • Bộ nhớ phụ: O(n) để lưu danh sách kết quả và tối đa n phần tử trong Min-Heap.
  • Lưu ý cài đặt:
    • Trong Java 21, khi viết hàm so sánh cho Arrays.sort(a, (u, v) -> ...), tuyệt đối không viết (int)(u[0] - v[0]) vì phép trừ hai số lớn hoặc số âm có thể gây tràn số nguyên (integer overflow) và làm sai thứ tự sắp xếp. Hãy luôn dùng Long.compare(u[0], v[0]) hoặc Integer.compare(u[0], v[0]).
    • Trong C++17, std::sort trên vector<pair<long long, long long>> tự động sắp xếp theo .first trước, nếu bằng nhau thì sắp theo .second, rất gọn gàng và an toàn.

Bảng phân loại nhanh 4 dạng bài khoảng thời gian trong phỏng vấn

Một điểm tinh tế mà người phỏng vấn rất thích hỏi là: "Khi nào ta sắp xếp theo mốc bắt đầu start, và khi nào phải sắp xếp theo mốc kết thúc end?" Bảng dưới đây giúp bạn phân biệt tức thì:

Dạng bài Tiêu chí sắp xếp chuẩn Tư duy tham lam / Cấu trúc dữ liệu Độ phức tạp
Gộp khoảng (Merge Intervals) Tăng dần theo start Giữ đoạn cuối cùng trong kết quả, nếu l <= last_r thì cập nhật last_r = max(last_r, r), nếu l > last_r thì thêm đoạn mới O(n log n)
Chèn khoảng (Insert Interval) Danh sách đã tăng sẵn theo start Chia 3 khúc: các đoạn kết thúc trước newL, các đoạn giao với [newL, newR], và các đoạn bắt đầu sau newR O(n) (không cần sort lại)
Đếm phòng họp (Meeting Rooms II) Tăng dần theo start (hoặc tách 2 mảng starts, ends riêng) Dùng Min-Heap lưu giờ kết thúc sớm nhất của các phòng đang mở, hoặc dùng kỹ thuật đường quét sự kiện +1 / -1 O(n log n)
Chọn nhiều đoạn rời nhau nhất (Non-overlapping / Minimum Arrows to Burst Balloons) Tăng dần theo end Tham lam chọn đoạn kết thúc sớm nhất để nhường tối đa không gian phía sau cho các đoạn kế tiếp O(n log n)

Hãy nhớ quy tắc vàng: khi cần hợp nhất tất cả những gì chạm nhau hoặc mô phỏng dòng thời gian từ trái sang phải, hãy sắp xếp theo start. Khi cần chọn được nhiều khoảng rời nhau nhất (hoặc bắn ít mũi tên nhất để xuyên qua mọi quả bóng), hãy sắp xếp theo end.

Các lỗi sai phổ biến và cách tự kiểm tra code

  1. Gán merged.back().second = r thay vì max(merged.back().second, r): Đây là lỗi kinh điển nhất. Với hai đoạn [1, 10] và [2, 5], nếu bạn gán thẳng mốc phải bằng 5, đoạn kết quả bị co ngắn lại thành [1, 5] và làm mất phần [5, 10].
  2. Sắp xếp lại toàn bộ mảng trong bài Insert Interval: Ở bài Insert Interval, đề bài đã cho sẵn danh sách các khoảng tăng dần và không chồng lấp. Nếu bạn nhét khoảng mới vào rồi gọi sort lại từ đầu, độ phức tạp bị đẩy lên O(n log n) thay vì O(n) như kỳ vọng của người phỏng vấn.
  3. Sai thứ tự ưu tiên tại cùng một thời điểm trong kỹ thuật đường quét (+1/-1): Nếu giải Meeting Rooms II bằng cách tách mỗi đoạn [l, r] thành hai sự kiện (l, +1) (mở phòng) và (r, -1) (trả phòng), khi hai sự kiện có cùng tọa độ thời gian (ví dụ một cuộc họp kết thúc lúc 10 và cuộc họp khác bắt đầu lúc 10), bạn bắt buộc phải xử lý sự kiện trả phòng (10, -1) trước sự kiện mở phòng (10, +1). Nếu xử lý +1 trước, biến đếm số phòng đang mở sẽ bị vọt lên dư 1 đơn vị tại đúng mốc chạm nhau.

Để tự kiểm tra code trước khi nộp, bạn có thể đối chiếu kết quả của thuật toán Min-Heap với cách đếm sự kiện đường quét (đặt (r, -1) đứng trước (l, +1) khi sắp xếp cặp (time, delta)) trên 4 trường hợp biên:

  • Danh sách rỗng n = 0 và danh sách chỉ có 1 đoạn.
  • Một đoạn lớn bao trùm nhiều đoạn nhỏ bên trong nhưng các đoạn nhỏ không giao nhau: [0, 30], [5, 10], [15, 20] (gộp ra 1 đoạn nhưng cần 2 phòng).
  • Hai đoạn chỉ chạm nhau ở đúng 1 điểm đầu mút: [1, 4] và [4, 5] (gộp thành [1, 5], số phòng chỉ cần 1).
  • Các đoạn có tọa độ trùng hệt nhau: [2, 5], [2, 5], [2, 5] (gộp thành 1 đoạn [2, 5], số phòng cần 3).

Luyện ngay trên Big-O Coding

Bạn có thể luyện tập ngay chuỗi bài toán gộp khoảng, chèn khoảng và chọn tập điểm nhỏ nhất chạm mỗi đoạn ít nhất hai lần (tham lam theo mốc kết thúc) trong lộ trình Coding Interview 150 dưới đây.

Câu hỏi thường gặp

Bài Meeting Rooms II ngoài cách dùng Min-Heap còn cách nào đạt O(n log n) mà code ngắn hơn không?

Có. Bạn có thể tách riêng toàn bộ n mốc bắt đầu vào mảng starts và n mốc kết thúc vào mảng ends, sau đó sắp xếp độc lập cả hai mảng. Dùng hai con trỏ i (duyệt starts) và j (duyệt ends): mỗi khi starts[i] >= ends[j], nghĩa là đã có một cuộc họp kết thúc để nhường phòng nên ta tăng j (tái sử dụng phòng); ngược lại ta tăng số phòng cần mở lên 1. Cách này không cần cấu trúc Heap và chạy rất nhanh trong thực tế.

Nếu đề bài yêu cầu giữ nguyên thứ tự xuất hiện ban đầu của các khoảng thì có sắp xếp được không?

Bản chất của hợp nhất khoảng là một quan hệ tương đương theo tính liên thông trên trục số, không phụ thuộc vào thứ tự nhập vào. Sau khi sắp xếp và gộp xong, các khoảng kết quả luôn đôi một rời nhau và tự động nằm theo thứ tự từ trái sang phải trên trục thời gian. Nếu đề bài yêu cầu biết những chỉ số gốc nào đã gộp vào nhau, bạn chỉ cần mang theo chỉ số ban đầu (l, r, original_idx) khi sắp xếp.

Làm sao kiểm tra nhanh hai khoảng [a, b] và [c, d] có giao nhau không mà không cần xét nhiều trường hợp?

Hai đoạn đóng [a, b] và [c, d] có phần giao khác rỗng khi và chỉ khi mốc bắt đầu lớn hơn không vượt quá mốc kết thúc nhỏ hơn: max(a, c) <= min(b, d) (ngược lại nếu max(a, c) > min(b, d) thì hai đoạn tách rời). Công thức một dòng này đúng cho mọi vị trí tương đối giữa hai đoạn (kể cả khi chưa sắp xếp ai đứng trước ai) và giúp code trong phòng phỏng vấn cực kỳ sáng sủa.

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483