इस समस्या में, हमें दो सरणियाँ दी जाती हैं जिनमें N मान होते हैं जो होटल में आगमन और प्रस्थान और एक पूर्णांक k को दर्शाते हैं। हमारा काम यह पता लगाना है कि दिए गए आगमन और प्रस्थान समय के साथ k बुकिंग संभव है या नहीं।
समस्या का विवरण: यहां, हमें यह जांचना होगा कि k कमरों वाला होटल सभी आगमन और प्रस्थान को समायोजित करने में सक्षम है या नहीं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: आगमन :{1 4 5 7}
प्रस्थान :{3 5 6 9}
के =1
आउटपुट: हाँ
समाधान दृष्टिकोण:
समस्या को हल करने के लिए, हम होटल के आगमन और प्रस्थान को एक सहायक सरणी में एक लेबल के साथ संग्रहीत करेंगे जो आगमन या प्रस्थान के लिए है। फिर इस सरणी को क्रमबद्ध करें और होटल के लिए सक्रिय बुकिंग की संख्या गिनें।
यदि आगमन हो तो गिनें++
यदि प्रस्थान हो, तो गिनें--.
यदि किसी भी समय बुकिंग k से अधिक है, तो गलत, . लौटाएं अन्य सत्य लौटाएं।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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 से अधिक है, तो झूठी वापसी करें। अन्यथा सही लौटें।
चूंकि, 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