数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用 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
更新于：2021年1月22日
259 次浏览
广告