Source: Hotel Bookings Possible

A hotel manager has to process N advance bookings of rooms for the next season. His hotel has Krooms. Bookings contain an arrival date and a departure date. He wants to find out whether there are enough rooms in the hotel to satisfy the demand. Write a program that solves this problem in time O(N log N) .

Input:


First list for arrival time of booking.
Second list for departure time of booking.
Third is K which denotes count of rooms.

Output:

A boolean which tells whether its possible to make a booking. 
Return 0/1 for C programs.
O -> No there are not enough rooms for N booking.
1 -> Yes there are enough rooms for N booking.

Example :

Input : 
        Arrivals :   [1 3 5]
        Departures : [2 6 8]
        K : 1

Return : False / 0 

At day = 5, there are 2 guests in the hotel. But I have only one room.

解題：

  1. 題目要求必須在時間複雜度O(n logn)之內依據訂房資訊（每位訂房者的預計入住日及退房日）以及飯店現有的房數計算是否會有房數供應不足的問題；
  2. 假設飯店共有5間房間，需設計一個機制能夠在顧客入住時自動將empty轉為occupied，並於退房時回復；
  3. 這題在思考時需拋棄＂個別顧客何時入住及退房＂的觀念：因每位房客的入住天數不一，在計算房數是否足夠時應只思考入住及退房的天數順序。舉例來說：
    • Arrivals :       [1 3  5  4 7]   => [1 3 4 5 7  ]
    • Departures : [2 6 10 6 9]   => [2 6 6 9 10]
    • K : 2   [0 0]
    • 在此情況下，到D5即會因為房客入住但現有房源尚未空出而發生房數不夠的情形。
  4. 如此一來，就只剩下如何比較入住及退房的數字順序了（while loop）

Code:

class Solution:
    # @param arrive : list of integers
    # @param depart : list of integers
    # @param K : integer
    # @return a boolean
    def hotel(self, arrive, depart, K):
        occupancy = 0
        n = len(arrive)
        if n == 1:
            if K > 0: return True
            else: return False
        elif n == 0: return True
        arrive = sorted(arrive)
        depart = sorted(depart)
       
        i, j = 0, 0
        while i < n and j < n:
            if arrive[i] < depart[j]:
                occupancy += 1
                if occupancy > K:
                    return False
                i += 1
            else:
                occupancy -= 1
                j += 1
        
        return True

想完之後才發現當初自己過的竟然是用for loop……但仔細一看for loop的解法是把入住跟退房併進同一個陣列裡面去做排序，而合併在一起的陣列做排序所需要的計算量在資料量大的時候會遠比兩個陣列分別排序耗用更多的計算資源，原則上不推薦，即是行數看起來比較少。有興趣的可以再自行參考InterviewBit提供的solution囉。

GitHub: GitHub

發表留言