Kiểm tra k đặt phòng khả thi với giờ đến/đi trong C++

Cho mảng giờ đến, giờ đi của N khách và số phòng k. Nhiệm vụ: kiểm tra k đặt phòng có khả thi không.

Mô tả: Khách sạn k phòng, kiểm tra có đáp ứng được tất cả lịch trình không.

Ví dụ:

Đầu vào: Arrivals: {1, 4, 5, 7}, Departures: {3, 5, 6, 9}, K = 1

Đầu ra: Yes

Phương pháp giải

Cách 1: Mảng sự kiện - Ghi nhận sự kiện đến (+1) và đi (-1), sắp xếp theo thời gian. Duyệt đếm số phòng đang dùng, nếu vượt k => false.

Cách 2: Sắp xếp riêng - Sắp xếp mảng đến và mảng đi riêng. Với mỗi khách đến thứ i, kiểm tra khách đến thứ i+k có đến trước khách đi thứ i không. Nếu có => vượt k phòng.

Chương trình minh họa (Cách 1)

Ví dụ

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

bool isBookingValid(int arrival[], int departure[], int n, int k) {
    vector<pair<int, int> > auxArray;
    int activeBookings = 0, maxBookings = 0;
    for (int i = 0; i < n; i++) {
        auxArray.push_back(make_pair(arrival[i], 1));
        auxArray.push_back(make_pair(departure[i], 0));
    }
    sort(auxArray.begin(), auxArray.end());
    for (int i = 0; i < auxArray.size(); i++) {
        if (auxArray[i].second == 1) {
            activeBookings++;
            maxBookings = max(maxBookings, activeBookings);
        } else
            activeBookings--;
    }
    return (k >= maxBookings);
}

int main() {
    int arrival[] = { 1, 4, 5, 7 };
    int departure[] = { 3, 5, 6, 9 };
    int k = 1;
    int n = sizeof(arrival) / sizeof(arrival[0]);
    if (isBookingValid(arrival, departure, n, k))
        cout << "All booking are possible";
    else
        cout << "Booking not possible";
    return 0;
}

Kết quả

All booking are possible

Chương trình minh họa (Cách 2)

Ví dụ

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

bool isBookingPossible(int arrival[], int departure[], int K, int N) {
    sort(arrival, arrival + N);
    sort(departure, departure + N);
    for (int i = 0; i < N; i++) {
        if (i + K < N && arrival[i + K] < departure[i])
            return false;
    }
    return true;
}

int main() {
    int arrival[] = { 1, 2, 3 };
    int departure[] = { 2, 3, 4 };
    int N = sizeof(arrival) / sizeof(arrival[0]);
    int K = 1;
    if (isBookingPossible(arrival, departure, K, N))
        cout << "All booking are possible";
    else
        cout << "Booking not possible";
    return 0;
}

Kết quả

All booking are possible