查找在C ++中有给定的到达和离开时间的k个预订是否可能
在这个问题中，我们得到了两个数组，它们分别是表示到达和离开酒店的N个值和一个整数k。我们的任务是查找在给定的到达和离开时间下是否可以进行k笔预订。
问题描述： 在这里，我们需要检查拥有k个房间的酒店是否能够容纳所有进出的旅客。
让我们举个例子来了解这个问题，
输入： 到达：{1457}
出发地：{3569}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