C++로 주어진 도착·출발 시간을 기준으로 k개의 예약 가능 여부 확인하기

이 문제에서는 호텔의 도착 시간과 출발 시간을 나타내는 N개의 값을 가진 두 개의 배열과 정수 k가 주어집니다. 우리의 과제는 주어진 도착 및 출발 시간 조건에서 k개의 예약이 모두 가능한지 확인하는 것입니다.

문제 설명: k개의 객실을 보유한 호텔이 모든 손님의 도착과 출발을 겹침 없이 수용할 수 있는지 판단해야 합니다.

예시를 통한 문제 이해

입력:

도착 시간(Arrivals): {1, 4, 5, 7}
출발 시간(Departures): {3, 5, 6, 9}
K = 1

출력: Yes

해결 접근 방법

문제를 해결하기 위해 호텔의 도착 및 출발 정보를 보조 배열(auxiliary array)에 저장하되, 각 값이 도착인지 출발인지 구분할 수 있는 라벨을 함께 붙입니다. 그런 다음 이 배열을 정렬하고 특정 시점의 활성 예약(active bookings) 수를 계산합니다.

• 도착인 경우 → count++
• 출발인 경우 → count--

어느 시점에서든 동시 예약 수가 k보다 많아지면 false를 반환하고, 끝까지 초과되지 않으면 true를 반환합니다.

솔루션 동작을 보여주는 프로그램

예제

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

출력

All booking are possible

다른 접근 방법

보조 배열을 사용하지 않고도 문제를 해결할 수 있습니다. 주어진 도착 배열과 출발 배열 두 개만 이용해 호텔의 예약 상황을 확인하는 방식입니다.

두 배열을 각각 정렬한 뒤 시간대가 겹치는 구간(overlapping)을 검사하여, 동시 예약 수가 k보다 커지면 false를 반환하고 그렇지 않으면 true를 반환합니다.

객실이 k개 있으므로, 더 간단한 방법은 k번째 도착 시간을 확인하는 것입니다. 정렬된 상태에서 (i + K)번째 도착 시간이 i번째 출발 시간보다 빠르다면, K+1명의 손님이 동시에 머무는 상황이 발생한다는 의미이므로 예약이 불가능합니다.

솔루션 동작을 보여주는 프로그램

예제

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

출력

All booking are possible