এই সমস্যায়, আমাদের 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 রিটার্ন করুন।
যেহেতু 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
