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.

Comments

Post a Comment

Popular posts from this blog

Planting flowers with no adjacent flower plots

Image
Problem Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule  Sample inputs  Input: 1,0,0,0,0,0,1,0,0  3 => true  4 => false  Input: 1,0,0,1,0,0,1,0,0  1 => true  2 => false  input: 0  1 => true  2 => false  public boolean canPlaceFlowers(List flowerbed, int numberToPlace) {  // Implementation here  }
Read more
  Given an array of  intervals  where  intervals[i] = [start i , end i ] , merge all overlapping intervals, and return  an array of the non-overlapping intervals that cover all the intervals in the input . Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.   Constraints: 1 <= intervals.length <= 10 4 intervals[i].length == 2 0 <= start i <= end i <= 10 4
Read more

Find the maximum number of bomb that can be detonated

  Problem You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb. The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range. You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range.  These bombs will further detonate the bombs that lie in their ranges. Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb. Input: bombs = [[2,1,3],[6,1,4]] Output: 2 Explanation: The above figure shows the positions and ranges of the 2 bombs. If we detonate the left bomb, the right bomb will not be affected. But if we detonate the right bomb, both bombs will be detonated. So...
Read more