ตรวจสอบการจองห้องพัก K ห้องได้หรือไม่จากเวลาเข้า-ออกใน C++

โจทย์

ได้รับอาร์เรย์เวลาเข้า (arrival) และเวลาออก (departure) ขนาด N และจำนวนห้อง k ทางเราต้อง ตรวจสอบว่าสามารถจองได้หรือไม่โดยไม่ให้เกิน k ห้องพร้อมกัน

ตัวอย่าง

Input: Arrivals = {1,4,5,7}, Departures = {3,5,6,9}, K = 1

Output: Yes

แนวทางแก้ปัญหา

วิธี 1: Event Timeline (Sweep Line)

สร้างอาร์เรย์เหตุการณ์: (เวลา, +1 สำหรับเข้า, -1 สำหรับออก)
เรียงตามเวลา (ถ้าเวลาเท่ากัน ให้การออกก่อน)
สะสมจำนวนห้องที่ใช้งาน หาค่าสูงสุด -> เปรียบเทียบกับ k

วิธี 2: Two Pointers (ประหยัดหน่วยความจำ)

เรียง arrival และ departure แยกกัน
ใช้ pointer i สำหรับ arrival, j สำหรับ departure
ถ้า arrival[i] < departure[j] -> เพิ่มห้อง, i++; ไม่เช่นนั้น -> ลดห้อง, j++
ตรวจสอบว่าห้องพร้อมกันเกิน k หรือไม่

โปรแกรมตัวอย่าง (วิธี 1)

#include <bits/stdc++.h>
using namespace std;

bool isBookingValid(int arrival[], int departure[], int n, int k) {
    vector<pair<int, int>> auxArray;
    for (int i = 0; i < n; i++) {
        auxArray.push_back({arrival[i], 1});
        auxArray.push_back({departure[i], 0});
    }
    sort(auxArray.begin(), auxArray.end());
    int activeBookings = 0, maxBookings = 0;
    for (auto& e : auxArray) {
        if (e.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, 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