Editorial for ptit042: Phòng thí nghiệm

Hiểu bài toán

Bài toán yêu cầu tìm số lượng phòng thí nghiệm tối thiểu cần thiết để安排 tất cả các lớp thực hành mà không bị chồng lấn về thời gian. Mỗi lớp thực hành có thời điểm bắt đầu và kết thúc. Một phòng chỉ có thể phục vụ một lớp tại một thời điểm. Vấn đề này tương đương với việc tìm số lượng lớp học đồng thời nhiều nhất trong cùng một thời điểm.

Các cách tiếp cận

Cách Sử dụng Priority Queue (Min Heap)

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

struct Class {
    int start, end;
    bool operator<(const Class& other) const {
        if (start != other.start) return start < other.start;
        return end < other.end;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<Class> classes(N);
    for (int i = 0; i < N; i++) {
        int G1, P1, G2, P2;
        cin >> G1 >> P1 >> G2 >> P2;
        classes[i].start = G1 * 60 + P1;
        classes[i].end = G2 * 60 + P2;
    }
    sort(classes.begin(), classes.end());

    priority_queue<int, vector<int>, greater<int>> pq;
    int ans = 0;
    for (const auto& cls : classes) {
        // Nếu phòng sớm nhất (pq.top()) kết thúc trước khi lớp này bắt đầu,
        // ta có thể tái sử dụng phòng đó.
        if (!pq.empty() && pq.top() <= cls.start) {
            pq.pop();
        }
        pq.push(cls.end);
        ans = max(ans, (int)pq.size());
    }
    cout << ans << "\n";
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Cách tiếp cận này mô phỏng việc sắp xếp các lớp vào các phòng một cách tối ưu.

1. Sắp xếp các lớp theo thời gian bắt đầu tăng dần.
2. Sử dụng Min Heap (Priority Queue) để lưu trữ thời gian kết thúc của các lớp đang được thực hành trong các phòng khác nhau. Top của heap luôn là thời gian kết thúc sớm nhất.
3. Duyệt qua từng lớp:
   • Kiểm tra xem lớp hiện tại có thể sử dụng phòng của lớp sắp kết thúc nhất không (thời gian bắt đầu >= thời gian kết thúc của phòng đó).
   • Nếu được, loại bỏ lớp cũ ra khỏi heap (giảm số phòng đang dùng) và thêm lớp mới vào.
   • Nếu không, phải mở một phòng mới (thêm vào heap).
   • Cập nhật kết quả là kích thước lớn nhất của heap.

Cách Sử dụng Sweep Line (Đếm sự kiện)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<pair<int, int>> events;
    for (int i = 0; i < N; i++) {
        int G1, P1, G2, P2;
        cin >> G1 >> P1 >> G2 >> P2;
        int start = G1 * 60 + P1;
        int end = G2 * 60 + P2;
        // Sự kiện bắt đầu (+1 phòng)
        events.push_back({start, 1});
        // Sự kiện kết thúc (-1 phòng)
        events.push_back({end, -1});
    }

    // Sắp xếp: theo thời gian tăng dần.
    // Nếu cùng thời điểm, xử lý sự kiện bắt đầu (+1) TRƯỚC sự kiện kết thúc (-1)
    // để đảm bảo nếu một lớp kết thúc ngay khi lớp khác bắt đầu, ta cần 2 phòng.
    sort(events.begin(), events.end(), [](auto &a, auto &b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    });

    int current_rooms = 0;
    int max_rooms = 0;
    for (auto &e : events) {
        current_rooms += e.second;
        max_rooms = max(max_rooms, current_rooms);
    }
    cout << max_rooms << "\n";
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Phương pháp Sweep Line là cách hiệu quả nhất để giải quyết bài toán đếm số lượng chồng lấn.

1. Biến mỗi khoảng thời gian thành 2 sự kiện: 'Bắt đầu' (mở rộng số phòng cần dùng) và 'Kết thúc' (giảm số phòng cần dùng).
2. Tạo một danh sách các sự kiện và sắp xếp chúng theo thời gian.
3. Quan trọng: Nếu có sự kiện bắt đầu và kết thúc xảy ra cùng một lúc, ta phải ưu tiên xử lý sự kiện bắt đầu trước. Điều này đảm bảo ta tính đúng số phòng tối thiểu khi một lớp kết thúc và lớp khác bắt đầu ngay lập tức (ví dụ: 08:13).
4. Duyệt qua danh sách sự kiện, duy trì một biến đếm số phòng hiện tại. Giá trị lớn nhất của biến đếm này chính là câu trả lời.

Cách Brute Force (Tìm kiếm tuần tự)

// Pseudocode cho cách tiếp cận Brute Force
// Không khuyến khích sử dụng cho N lớn

int solve_brute_force(vector<Class> classes) {
    int n = classes.size();
    int max_overlap = 0;
    // Kiểm tra mọi điểm thời gian có thể (điểm bắt đầu của các lớp)
    for (int i = 0; i < n; i++) {
        int time_point = classes[i].start;
        int current_overlap = 0;
        for (int j = 0; j < n; j++) {
            if (classes[j].start <= time_point && time_point < classes[j].end) {
                current_overlap++;
            }
        }
        max_overlap = max(max_overlap, current_overlap);
    }
    return max_overlap;
}

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất nhưng không hiệu quả.

1. Với mỗi lớp, ta lấy thời điểm bắt đầu của nó làm mốc.
2. Đếm xem có bao nhiêu lớp đang diễn ra tại mốc thời gian đó.
3. Lấy giá trị lớn nhất. Cách này chỉ khả thi với N nhỏ (< 1000) và sẽ bị Timeout với N = 10^5.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán tìm số phòng tối thiểu tương đương bài toán tìm số lượng lớp học đồng thời (max overlap) nhiều nhất.
• Thuật toán Sàn lọc (Sweep Line) là công cụ mạnh mẽ cho các bài toán tính toán trên các đoạn thời gian.
• Nếu chỉ cần biết số lượng, ta không cần gán cụ thể từng phòng, chỉ cần đếm số lượng.

Lỗi thường gặp

• Xử lý sai các sự kiện cùng thời điểm: Nếu một lớp kết thúc lúc 10:00 và lớp khác bắt đầu lúc 10:00, nếu ta xử lý sự kiện kết thúc trước, ta sẽ lầm tưởng có thể dùng lại phòng đó. Thực tế ta cần 2 phòng. Do đó, ưu tiên sự kiện bắt đầu (+1) trước sự kiện kết thúc (-1) khi sắp xếp.
• Chuyển đổi sai định dạng thời gian: Cần quy về cùng một đơn vị (ví dụ phút) để so sánh, ví dụ: Giờ * 60 + Phút.