C++で指定された到着時刻と出発時刻でk件の予約が可能かどうかを確認します

この問題では、ホテルへの到着と出発を示すN個の値と整数kで構成される2つの配列が与えられます。私たちの仕事は、指定された到着時刻と出発時刻でk件の予約が可能かどうかを確認することです。

問題の説明： ここでは、k室のホテルがすべての到着と出発に対応できるかどうかを確認する必要があります。

問題を理解するために例を見てみましょう

入力： 到着：{1 4 5 7}

出発：{3 5 6 9}
K =1

出力： はい

ソリューションアプローチ：

この問題を解決するために、ホテルの到着と出発を、到着または出発用のラベルが付いた補助配列に格納します。次に、この配列を並べ替えて、ホテルのアクティブな予約の数を数えます。

到着した場合、カウント++
出発する場合は、数えます-。

いつでも予約が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

別のアプローチ：

補助アレイの使用をなくすことができます。出発と到着に指定された2つの配列を使用して、ホテルの予約を確認できます。

次に、重複を確認し、それがkより大きい場合は、falseを返します。それ以外の場合はtrueを返します。

kの部屋があるので、簡単なアプローチはk ^th をチェックすることです。 到着し、範囲内にあるかどうかを確認します。

ソリューションの動作を説明するプログラム

例

#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