Tìm xem có thể đặt trước k với thời gian đến và đi đã cho bằng C ++ hay không

Trong bài toán này, chúng ta đưa ra hai mảng gồm N giá trị biểu thị việc đến và đi tại khách sạn và một số nguyên k. Nhiệm vụ của chúng tôi là tìm xem có thể đặt trước k với thời gian đến và đi đã cho.

Mô tả sự cố: Ở đây, chúng ta cần kiểm tra xem khách sạn có k phòng có đủ sức chứa tất cả các lượt khách đến và đi hay không.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: Lượt đến:{1 4 5 7}

Khởi hành:{3 5 6 9}
K =1

Đầu ra: Có

Cách tiếp cận giải pháp:

Để giải quyết vấn đề, chúng tôi sẽ lưu trữ thời gian đến và đi của khách sạn trong một mảng phụ trợ với nhãn ghi là khách đến hoặc đi. Sau đó, sắp xếp mảng này và đếm số lượng đặt phòng đang hoạt động cho khách sạn.

Nếu đến, tính ++
Nếu khởi hành, tính--.

Nếu tại bất kỳ thời điểm nào, lượt đặt trước nhiều hơn k, hãy trả về false, khác trả về true.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

All booking are possible

Cách tiếp cận khác:

Chúng ta có thể loại bỏ việc sử dụng mảng phụ trợ. Chúng tôi có thể kiểm tra các đặt phòng của khách sạn bằng cách sử dụng hai mảng được đưa ra là khởi hành và đến.

Sau đó kiểm tra chồng chéo và nếu nó lớn hơn k, trả về false. Trả lại true.

Vì có k phòng, một cách tiếp cận dễ dàng sẽ là kiểm tra k ^th đến và kiểm tra xem nó có nằm trong phạm vi không.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

All booking are possible