Managing the conference rooms with balancing the occupancy percentage

Problem

Given the list of conference rooms with the capacity and the target occupancy percentages,

write the program that maintains the balanced occupancy percentage across the rooms.

Input: list of rooms { [30, 0.6], [50, 0.7], [90, 0.4]}, number of guests

Output: list of rooms with balanced occupancy percentages across the rooms

Answer

Initial approach using Minheap, $O( N \log_2 N)$, N = number of guests

One way to keep the balanced occupancy ratio is to keep the rooms in the MinHeap ordered by occupancy ratio.

1) for each guest from $N$, pull the least occupied room and assign the guest.
2) Once the assignment is done, put it back into the minheap.

3) return the list of rooms after all iterations.

Minheap ensure both extract() and add() operation to be done in $O(\log_2 N)$.


Here is the complete code in C++


Practice statistics:

19:00: to write up the code
24:00: to write up the MaxHeap. (could not find the one logical flaw)


Better approach via arithmetic calculation, $O(1)$

This time, I decided to find a better way to allocate the guests. In this approach, the guests are split to each room to proportional to  $$\frac{room\,capacity}{all\,capacity}$$.
In this way, we can allocate guests to each room evenly.
Assumptions made for this approach are the followings:

1. The goal is to keep the balanced occupancy percent as long as none of the rooms meets the target occupancy rate
2. Once the target occupancy rate is met, other rooms should be assigned guests. the balanced occupancy will be no longer kept.
3. If all rooms met the occupancy target, we will not assign guests to the room anymore.

Here is the solution running in $O(1)$. This code handles the case where there are more guests than the target occupancy percentage once. It needs to be decided what to do when all rooms reached the target occupancy percentage.

Practice statistics

12:05: for algorithm
27:48: to write up the code.  (No bug)
01:45: to fix up the output format and python division (rounding up to the nearest whole number)

UPDATE(2022-06-18): Solve the problem with MaxHeap by sorting the room by remaining capacity percent (%). This time I changed the input pattern for the guests into an array. The question itself does not mention whether quests are coming all at once.

Add to handle the case where the room with the largest remaining capacity can't accommodate the event and choose the next one which can.

10:44: algorithm

22:57: to write the main logic without the full MaxHeap implementation

15:06: to write up the MaxHeap and fix the bug.