資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告