US Interview Question
Computer ScientistsCountry: United States
Interview Type: Written Test
A hotel manager has to process n advance bookings of rooms for the next season. His hotel has k identifical rooms. Bookings contain
an arrival date and a departure date. He wants fo find out whether there are enough rooms in the hotel to satify the demand.
Design an algorithm that solves this problem in time O(n logn) . Hint:Consider the set off all arrivals and departures .
Sort the set and process it in sorted order.
Made in Merge Sort
//assume dates can be represented by an int
boolean enoughRooms(int capacity k; List<Bookings> bookings) {
int[] arrivals = new int[bookings.size()];
int[] departures = new int[bookings.size()];
int i = 0;
for(Booking booking: bookings) {
arrivals[i] = booking.getArrivalTime();
departures[i] = booking.getDepartureTime();
i++;
}
PriorityQueue arrivalQueue = minHeapify(arrivals); //O(n) operation
PriorityQueue departureQueue = minHeapify(departures);
int roomsTaken = 0;
//whole loops is O(nlogn)
while(!arrivalQueue.isEmpty()) {
if(arrivalQueue.peek() <= departureQueue.peek()) {
arrivalQueue.pop();
roomsTaken++;
if(roomsTaken > k) return false;
} else {
departureQueue.pop();
roomsTaken--;
}
}
return true;
}
I'm assuming that there is a Booking class with an interface like
I'm also assuming that the departure date must be later than the arrival date.
Here is an O(nlog(n)) solution:
Note that the bottleneck is the sorting, everything else is simply O(n). So if you use a linear sorting algorithm instead (counting sort seems like a reasonable choice, especially if the season doesn't have too many days and you expect many people to arrive/leave on the same day), you get an O(n) algorithm.
- djmclaugh September 02, 2014