Normal Hotel Booking Possible Problem can be worked out in O(NlogN), but I encountered a variant of Hotel Booking Possible Problem and I couldnt work out a solution less thant O(NM).
The Problem : A hotel manager is trying to manage hotel booking for next M days with N bookings. For some reason, the number of available room for each day is different. You are given an array of rooms[M] where rooms[i] represents the number of rooms available on day i, and a list of bookings contains number of rooms required, start time and end time (inclusive). If all bookings are possible, the algorithm returns the number of bookings. If booking fails, the algorithm returns the index of booking that failed first.
Given Data : int[M] rooms
- rooms[i] rooms available on day i int[N][3] bookings
- bookings[j][0] rooms required for booking j
- bookings[j][1] start day -bookings[j][2] end day
Return : Number of bookings if all possible. Index of booking that fails first
Example :
rooms : 2 8 5 8
bookings :
2 0 2
1 1 2
5 1 3
3 2 3
return: 2
Explain : The bookings[0] requires 2 rooms, starts from day 0 and ends on day 2 (inclusive). After bookings[0], the rooms avaliable becomes [0 6 3 8].Similary, after booking[1], the rooms available becomes [0 5 2 8]. For booking[2], there is not enough rooms because rooms[2] = 2 less than rooms required for booking[2], which is 5. Thus we return the index of failed booking 2.
It is very easy to come out a solution that works in O(NM)
for(int i = 0 ;i < bookings.length; i ){
int roomRequired = bookings[i][0];
int start = booking[i][1];
int end = booking[i][2];
for(int j = start; j <= end; j ){
rooms[j] -= roomRequired;
if(rooms[j] < 0 ) return i;
}
}
return bookings.length;
And it is easy to get first day that fails
int helper = new int[rooms.length 1];
for(int i = 0 ;i < bookings.length; i ){
int roomRequired = bookings[i][0];
int start = booking[i][1];
int end = booking[i][2];
helper[start] = roomRequired;
helper[end 1] -= roomRequired;
}
int bookingSum = 0;
for(int i = 0; i < rooms.length; i ){
bookingSum = helper[i];
if(rooms[i] < bookingSum) return i;
}
But I could not figure out how to get the first index of booking that fails in less than O(MN) because the first day that fails does not necessarily caused by the first fail of booking.
CodePudding user response：
Just a general idea.
First, turn each booking into a pair of events. Booking starts, booking ends.
Sort events by time.
Now we walk through time keeping track of the following:
- Number of bookings open.
- Dictionary of which bookings are open.
- How many bookings are available each day.
If we arrive at a day with too many bookings, what we do is look at all of the bookings open on that day (which we have in a dictionary) sort by start, then walk through until we come to the number of bookings we have days.
The very next booking is the first booking to make that fails.
This will be O(n log(n)).
CodePudding user response：
O(N M) solution: Stick deltas in an array of size M, counting changes in capacity as deltas. Then parse the array. Ruby code below.
irb(main):001:1* def bookings(rooms, bookings)
irb(main):002:1* booking_changes = [0] * bookings.size
irb(main):003:1*
irb(main):004:2* bookings.each do |booking|
irb(main):005:2* num_rooms = booking[0]
irb(main):006:2* start_day = booking[1]
irb(main):007:2* end_day = booking[2]
irb(main):008:2* booking_changes[start_day] = num_rooms
irb(main):009:2* booking_changes[end_day] -= num_rooms
irb(main):010:1* end
irb(main):011:1*
irb(main):012:2* 1.upto(rooms.size - 1) do |day|
irb(main):013:2* booking_changes[day] -= (rooms[day] - rooms[day - 1])
irb(main):014:1* end
irb(main):015:1*
irb(main):016:1* rooms_available = bookings[0][0]
irb(main):017:1*
irb(main):018:2* 0.upto(booking_changes.size - 1) do |day|
irb(main):019:2* rooms_available -= booking_changes[day]
irb(main):020:2* return day if rooms_available < 0
irb(main):021:1* end
irb(main):022:1*
irb(main):023:1* return -1
irb(main):024:0> end
=> :bookings
irb(main):025:0>
irb(main):026:0> bookings([2,8,5,8], [[2,0,2], [1,1,2], [5,1,3], [3,2,3]])
=> 2