C++ में दिए गए आगमन और प्रस्थान समय के साथ k बुकिंग संभव है या नहीं जांचें

इस समस्या में, हमें N मानों वाली दो सरणी दी गई हैं जो होटल में आगमन और प्रस्थान को दर्शाती हैं और एक पूर्णांक k। हमारा कार्य दिए गए आगमन और प्रस्थान समय के साथ k बुकिंग संभव है या नहीं जांचना है।

समस्या विवरण: यहां, हमें जांचना है कि k कमरों वाला होटल सभी आगमन और प्रस्थान को समायोजित करने में सक्षम है या नहीं।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट: Arrivals : {1 4 5 7}

Departures : {3 5 6 9} K = 1

आउटपुट: Yes

समाधान दृष्टिकोण:

समस्या को हल करने के लिए, हम होटल के लिए आगमन और प्रस्थान को एक लेबल के साथ सहायक सरणी में संग्रहीत करेंगे कि यह आगमन के लिए है या प्रस्थान। फिर इस सरणी को सॉर्ट करें और होटल के लिए सक्रिय बुकिंग की संख्या गिनें।

यदि आगमन, count++
यदि प्रस्थान, count--।

यदि किसी भी बिंदु पर किसी भी समय बुकिंग 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