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++

	#include <vector>
	#include <math.h>
	#include <iostream>
	using namespace std;
	struct room {
	int cap;
	int avail;
	int left;
	double ratio;
	double cur_ratio;
	room(int c, double r):cap(c), ratio(r), cur_ratio(0) {
	left = avail = (double) cap * ratio;
	cur_ratio = (double)left/(double)avail;
	}
	void add()
	{
	left--;
	cur_ratio = (double)left/(double)avail;
	cout<<"cur_ratio : " << cur_ratio<<endl;
	}
	void print()
	{
	cout<<"[ max : "<<cap<< " guests: "<<avail-left<<" target : ";
	cout<< ratio << " current ratio: " << cur_ratio<<" occupancy rate: ";
	cout<<(double)(avail-left)/cap<<" ]"<<endl;
	}
	};
	class Maxheap {
	public:
	void insert(room *r)
	{
	list.push_back(r);
	BubbleUp(list.size()-1);
	}
	room* extract ()
	{
	if (!list.size())
	return 0;
	room * r = list[0];
	swap(0, list.size()-1);
	list.pop_back();
	Heapify(0);
	return r;
	}
	private:
	int left(int p) {return 2*p +1; }
	int right(int p) {return 2*p +2; }
	int parent(int c) {return floor((double) (c-1)/2);}
	void swap(int s, int d)
	{
	room * tmp = list[s];
	list[s] = list[d];
	list[d] = tmp;
	}
	bool is_child(int p, int c)
	{
	return list[p]->cur_ratio > list[c]->cur_ratio;
	}
	void Heapify(int p)
	{
	int largest = p;
	int l = left(p);
	int r = right(p);
	if (l < list.size() && !is_child(largest, l))
	largest = l;
	if (r < list.size() && !is_child(largest, r))
	largest = r;
	if (largest != p)
	{
	swap(p, largest);
	Heapify(largest);
	}
	}
	void BubbleUp(int c)
	{
	if (c == 0)
	return;
	int p = parent(c);
	if (!is_child (p, c))
	{
	swap(p, c);
	BubbleUp(p);
	}
	}
	vector<room *> list;
	};
	void manage_rooms(int guests, vector<room*> rooms)
	{
	Maxheap heap;
	int i = 0;
	for(i = 0; i<rooms.size(); i++)
	heap.insert(rooms[i]);
	for (i = 0; i < guests; i++)
	{
	room * r = heap.extract();
	r->add();
	heap.insert(r);
	}
	}
	int main()
	{
	vector<room*> inputs;
	inputs.push_back(new room(30, 0.6));
	inputs.push_back(new room(50, 0.7));
	inputs.push_back(new room(90, 0.4));
	manage_rooms(60, inputs);
	for(int i = 0; i < inputs.size(); i++)
	{
	inputs[i]->print();
	}
	}

view raw manage_room.cpp hosted with ❤ by GitHub

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.

	class Room:
	def __init__(self, capacity, target):
	self.cap = capacity
	self.target = target
	self.count = 0
	self.target_count = int(self.cap * self.target)
	def occupancy(self):
	return self.count *1.0 / self.cap
	def assign(self, guests):
	spillover = 0
	to_assign = 0
	if guests + self.count > self.target_count:
	to_assign = self.target_count - self.count
	spillover = guests - to_assign
	else:
	to_assign = guests
	self.count += to_assign
	return spillover
	def is_full(self):
	return self.count == self.target_count
	class Scheduler:
	def schedule(self, input, num_guests):
	rooms = []
	total_cap = 0
	for r in input:
	rooms.append(Room(r[0], r[1]))
	total_cap += r[0]
	spillover = 0
	for r in rooms:
	to_assign = int(num_guests * r.cap/total_cap)
	spillover += r.assign(to_assign)
	#split split over among rooms that is not full yet.
	if spillover > 0:
	for r in rooms:
	if r.is_full() != True:
	to_assign = int(num_guests * r.cap/total_cap)
	spillover -= to_assign
	spillover += r.assign(to_assign)
	result =[]
	for r in rooms:
	result.append([r.cap, r.target, r.count, r.occupancy()])
	return result
	scheduler = Scheduler()
	rooms = [[30, 0.6], [50, 0.7], [90, 0.4]]
	num_guests = 60
	print("input = {} num_guests = {} output = {}".format(rooms, num_guests, scheduler.schedule(rooms, num_guests)))

view raw facebook_manage_rooms_with_balanced_ratio.py hosted with ❤ by GitHub

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.

	import json
	class Room:
	def __init__(self, capacity, target):
	self.cap = capacity
	self.target = target
	self.actual = 0
	self.remaining = int(capacity * target)
	self.remaining_percent = 1 - self.actual/self.remaining
	def add(self, num):
	self.actual += num
	self.remaining_percent = 1 - self.actual/self.remaining
	def get_remaining(self):
	return self.remaining - self.actual
	def get_remaining_percent(self):
	return self.remaining_percent
	def __str__(self):
	o = {
	'max_capacity': self.cap,
	'target': self.target,
	'actual': self.actual,
	'target_cap': self.remaining,
	'remaining' : self.get_remaining(),
	'remaining_cap(%)': self.remaining_percent
	}
	return json.dumps(o)
	class MaxHeap:
	def __init__(self):
	self.list = [None]
	def length(self):
	return len(self.list) - 1
	def parent(self, child):
	return child // 2
	def left(self, parent):
	return 2* parent
	def right(self, p):
	return 2 * p + 1
	def is_child(self, p, c):
	return self.list[p].get_remaining_percent() > self.list[c].get_remaining_percent()
	def swap(self, src, dst):
	tmp = self.list[src]
	self.list[src] = self.list[dst]
	self.list[dst] = tmp
	def extract(self):
	if len(self.list) <= 1:
	return None
	value = self.list[1]
	self.swap(1, len(self.list) - 1)
	self.list.pop()
	self.bubble_down(1)
	return value
	def add(self, value):
	self.list.append(value)
	self.bubble_up(len(self.list) - 1)
	def bubble_down(self, p):
	left = self.left(p)
	if left > self.length():
	return
	right = self.right(p)
	to_swap = left if right > self.length() or self.is_child(left, right) else right
	if self.is_child(p, to_swap) != True:
	self.swap(p, to_swap)
	self.bubble_down(to_swap)
	def bubble_up(self, c):
	parent = self.parent(c)
	if parent < 1:
	return
	if self.is_child(parent, c) != True:
	self.swap(parent, c)
	self.bubble_up(parent)
	class ManageRoom:
	def __init__(self, rooms):
	self.heap = MaxHeap()
	self.rooms=[]
	for r in rooms:
	room = Room(r[0], r[1])
	self.heap.add(room)
	self.rooms.append(room)
	def schedule_event(self, events):
	for e in events:
	unfits = []
	while self.heap.length() > 0:
	largest = self.heap.extract()
	if largest.get_remaining() < e:
	unfits.append(largest)
	else:
	largest.add(e)
	self.heap.add(largest)
	break
	if self.heap.length() == 0:
	raise Exception("can't accomodate the event ={}".format(e))
	for unfit in unfits:
	self.heap.add(unfit)
	def print_rooms(self):
	for r in self.rooms:
	print(r)
	# test
	rooms =[[30, 0.6], [50, 0.7], [90, 0.4]]
	events = [3, 4, 6, 7, 20, 11, 10, 3, 2]
	manager = ManageRoom(rooms=rooms)
	manager.schedule_event(events=events)
	manager.print_rooms()

view raw managing_room_capacity.py hosted with ❤ by GitHub

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.