Algorithm that uses Java PriorityQueue

http://ErikDMueller.com
https://github.com/Erik-D-Mueller/meeting-Rooms-Required-Algorithm-using-PriorityQueue

I was asked to white-board this problem at an interview:

Suppose an event company is planning to serve food to many different groups of people in an event space and the number of tables required must be known and set up before the event. Each group of people will require their own table while they're eating and will arrive and leave at a predetermined known time. Given a multidimensional input array of arrival times and their correlated departure times, calculate how many tables the event company should set up. In other words, what is the maximum number of tables that will be occupied at the same time during the night?

The solution that I have come up with is thus:

Think of the problem similar to a club with a door-man who is supposed to keep track of how many people are inside the building in order to not violate the maximum capacity. The door-man doesn't need to know who the people are or how long they plan to stay, the door-man only knows that there are zero patrons inside when they first open and after that he increments up the number of patrons inside when someone enters and decrements down the number of patrons inside when someone exits.

That's the key to the problem, realizing that we don't need to keep the arrival times coupled to their respective departure times, we can completely decouple them.

I designed an algorithm that operates like the door-man at a club, we take the multidimensional array of input data and we put all the arrival times into one priority-queue and all the departure times into another priority queue.

The priority queues naturally sort into ascending order which in this case represents earliest to latest in time.

After we have our priority queue of arrival times and departure times ready to be processed, we begin with the number of tables being occupied at zero and use .peek() to see which queue has a smaller head element, which indicates to us what event will occur next: an arrival or a departure.

If the next event to occur is an arrival then we increment up the number of tables being used and then use .poll() to remove that element since we have processed it.

If the next event to occur is a departure then we decrement down the number of tables being used and remove that element.

If the next element in both queues has the same value, that indicates that there is an arrival and a departure occurring at the same time and thus they cancel each other out and the number of tables being used is unchanged. We simply remove that element from both queues since they both have been processed.

We keep operating like this, processing and removing the lower value element from the two priority queue heads and in addition to keeping a running tally of how many tables are being occupied at any given time we also keep a peak value.

If we are only interested in the peek number of tables being occupied then we are done once the arrival times queue has been emptied because the number of tables being used cannot increase if there are no more arrivals.

I decided to keep processing until both queues are empty though, in case we want to see how many tables are being used at any time all the way up to close.

I wasn't actually given any input array so I have one method that generates the input array of time values using an argument for number of parties and an argument for number of time increments in the day, then I have another method that accepts the array as an argument and actually implements the algorithm.
Be aware that priority queue collection uses a priority-heap and not a sorted-list which means that only the head element is guaranteed to be highest priority, the elements after the head are not in any guaranteed order. There is no guaranteed ordered traversal on the prioroity queue collection and the elements after the head will appear random if you look at them in a debugger. If a developer wants guaranteed ordered traversal they should probably use an ArrayList with a .sort()

There is a fair amount of console formatting in order to conceptually output everything that I have described here.

.poll() returns null when the queue is empty which is better than .remove() which throws an exception but I still have to verify the queues are not empty because trying to compare a null value will still throw an exception.

Solving this problem with brute force could be implemented in 20 minutes which I cover in the beginning of the video but would have a horrendous growth rate

I've designed hundreds of algorithms like this in the software boot-camp that I attended I just haven't posted things like that here.