ค้นหาว่าสามารถจอง k ได้หรือไม่พร้อมเวลามาถึงและออกเดินทางที่กำหนดใน C++

ในปัญหานี้ เราได้รับสองอาร์เรย์ซึ่งประกอบด้วยค่า N ที่แสดงถึงการมาถึงและออกจากโรงแรมและจำนวนเต็ม k งานของเราคือ ค้นหาว่าสามารถจองได้ k ครั้งหรือไม่ตามเวลามาถึงและออกเดินทางที่กำหนด

คำอธิบายปัญหา: ที่นี่เราต้องตรวจสอบว่าโรงแรมที่มี k ห้องสามารถรองรับขาเข้าและขาออกทั้งหมดได้หรือไม่

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: ขาเข้า :{1 4 5 7}

ออกเดินทาง :{3 5 6 9}
K =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

แนวทางอื่น:

เราสามารถกำจัดการใช้อาร์เรย์เสริมได้ เราตรวจสอบการจองโรงแรมได้โดยใช้ 2 แถวที่ให้ไว้สำหรับการเดินทางขาเข้าและขาออก

จากนั้นตรวจสอบการทับซ้อนกันและถ้ามากกว่า 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