查找在C ++中有给定的到达和离开时间的k个预订是否可能

在这个问题中，我们得到了两个数组，它们分别是表示到达和离开酒店的N个值和一个整数k。我们的任务是查找在给定的到达和离开时间下是否可以进行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

另一种方法： 

我们可以消除使用辅助数组。我们可以使用给定的两个数组检查出发和到达的酒店预订情况。

然后检查重叠，如果它大于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