【C++】到着時刻・出発時刻が与えられたとき、k部屋の予約がすべて成立するか判定する方法

この問題では、ホテルへの到着時刻と出発時刻を表す N 個の値からなる2つの配列と、整数 k が与えられます。求めるのは、k 部屋のホテルですべての予約（到着・出発）を受け入れられるかどうかの判定です。

問題の概要

ホテルには k 室しかありません。そのため、複数の予約の滞在期間が重なり、同時に必要となる部屋数が k を超える場合は予約をすべて受け入れることができません。逆に、どの時点でも必要な部屋数が k 以内に収まるのであれば、すべての予約は成立します。

入出力例

入力：

Arrivals   : {1, 4, 5, 7}
Departures : {3, 5, 6, 9}
K = 1

出力：

Yes

この例では K = 1（客室は1部屋のみ）ですが、どの時点でも滞在が重ならないため、すべての予約が可能です。

解法アプローチ①：補助配列を使う方法

基本的な考え方は次のとおりです。

1. 各到着時刻と出発時刻を、それが「到着」か「出発」かを示すラベル付きで補助配列に格納する。
2. 補助配列を時刻順にソートする。
3. 配列を先頭から走査し、その時点でのアクティブな予約数（使用中の部屋数）をカウントする。
   ・到着イベント → カウント +1
   ・出発イベント → カウント −1

走査中にアクティブな予約数の最大値を記録しておき、その最大値が k 以下であれば true（全予約可能）、k を超えていれば false（予約不可）を返します。

実装例

#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;

    // 到着はラベル1、出発はラベル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;
}

出力

All booking are possible

この方法の計算量は、ソートに O(N log N)、走査に O(N) かかるため、全体として O(N log N) となります。

解法アプローチ②：補助配列を使わない方法

補助配列を作らず、与えられた2つの配列だけで判定することもできます。

まず、到着時刻の配列と出発時刻の配列をそれぞれ独立にソートします。すると、「i 番目に出発する宿泊客より後に到着する (i+K) 番目の宿泊客」が存在し、かつその到着時刻が i 番目の出発時刻より早い場合、少なくとも K+1 人が同時に滞在していることになります。

つまり、以下の条件を満たす i が1つでも存在すれば、K 部屋では足りず false を返します。

arrival[i + K] < departure[i]

この条件は「(i+K+1) 人目の到着が、(i+1) 人目の出発より早い＝K+1 室が必要」という状況を意味します。ループを最後まで回って条件に該当しなければ true を返します。

実装例

#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++)
    {
        // (i+K) 番目の到着が i 番目の出発より早い場合、
        // K+1 室以上が必要になるため予約不可
        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;
}

出力

All booking are possible

まとめ

どちらの方法もソートがボトルネックとなり O(N log N) の計算量ですが、アプローチ②は余分なメモリを消費しないため、メモリ効率を重視する場面で有効です。一方、最大同時予約数そのものを知りたい場合はアプローチ①が便利です。