এই সমস্যায়, আমাদেরকে হোটেলে আগমন এবং প্রস্থান নির্দেশ করে N মান নিয়ে গঠিত দুটি অ্যারে দেওয়া হয়েছে এবং একটি পূর্ণসংখ্যা k। আমাদের কাজ হল প্রদত্ত আগমন এবং প্রস্থান সময়ের সাথে k বুকিং করা সম্ভব কিনা তা খুঁজে বের করা।
সমস্যা বর্ণনা: এখানে, k রুম সহ হোটেলটি সমস্ত আগমন এবং প্রস্থানের ব্যবস্থা করতে সক্ষম কিনা তা আমাদের পরীক্ষা করতে হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: আগমন :{1 4 5 7}
প্রস্থান :{3 5 6 9}
কে =1
আউটপুট: হ্যাঁ
সমাধান পদ্ধতি:
সমস্যা সমাধানের জন্য, আমরা হোটেলের জন্য আগমন এবং প্রস্থান একটি অক্জিলিয়ারী অ্যারেতে একটি লেবেল সহ সংরক্ষণ করব যে এটি আগমন বা প্রস্থানের জন্য। তারপর এই অ্যারেটি সাজান এবং হোটেলের জন্য সক্রিয় বুকিংয়ের সংখ্যা গণনা করুন।
যদি আগমন, গণনা++
যদি প্রস্থান, গণনা--.
যেকোন সময়ে বুকিং k এর বেশি হলে, false, ফেরত দিন অন্যথায় সত্য ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
