Meeting Rooms II - Số phòng họp tối thiểu

Cho mảng khoảng thời gian họp [[s1,e1],[s2,e2],...] (si < ei). Tìm số phòng họp tối thiểu để không có xung đột.

Ví dụ: [[0,30],[5,10],[15,20]] → 2 phòng.

Giải thuật (Min-heap / Priority Queue)

Sắp xếp các khoảng theo thời gian bắt đầu. Dùng min-heap lưu thời gian kết thúc của các phòng đang dùng. Với mỗi họp: gỡ các phòng đã kết thúc (top ≤ start), thêm họp hiện tại vào heap. Kích thước heap max là đáp án.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

struct Comparator {
    bool operator()(vector<int>& a, vector<int>& b) {
        return a[1] > b[1]; // min-heap theo end time
    }
};

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        priority_queue<vector<int>, vector<vector<int>>, Comparator> pq;
        sort(intervals.begin(), intervals.end());
        int ret = 0;
        for (auto& iv : intervals) {
            while (!pq.empty() && pq.top()[1] <= iv[0])
                pq.pop();
            pq.push(iv);
            ret = max(ret, (int)pq.size());
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> v = {{0,30},{5,10},{15,20}};
    Solution ob;
    cout << ob.minMeetingRooms(v);
    return 0;
}

Đầu vào

{{0, 30}, {5, 10}, {15, 20}}

Đầu ra

2