C++에서 주어진 도착 및 출발 시간으로 k개의 예약이 가능한지 확인

이 문제에서는 호텔의 도착과 출발을 나타내는 N개의 값과 정수 k로 구성된 두 개의 배열이 제공됩니다. 우리의 임무는 주어진 도착 및 출발 시간에 k개의 예약이 가능한지 찾는 것입니다.

문제 설명: 여기에서 k 개의 객실이 있는 호텔이 모든 도착 및 출발을 수용할 수 있는지 확인해야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력: 도착:{1 4 5 7}

출발 :{3 5 6 9}
K =1

출력: 예

해결 방법:

이 문제를 해결하기 위해 호텔의 도착 및 출발을 도착 또는 출발을 위한 레이블과 함께 보조 배열에 저장합니다. 그런 다음 이 배열을 정렬하고 호텔의 활성 예약 수를 계산합니다.

도착하면 카운트++
출발하는 경우 계산--.

어느 시점에서든 예약이 k 이상인 경우 거짓, 을 반환합니다. 그렇지 않으면 참을 반환합니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#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

또 다른 접근 방식:

보조 배열의 사용을 없앨 수 있습니다. 출발과 도착에 대해 주어진 두 개의 배열을 사용하여 호텔의 예약을 확인할 수 있습니다.

그런 다음 겹침을 확인하고 k보다 크면 false를 반환합니다. 그렇지 않으면 true를 반환합니다.

k개의 방이 있으므로 k ^번째 를 확인하는 쉬운 방법이 있습니다. 도착하고 범위에 속하는지 확인하십시오.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#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