Counting rooms problem

You are the event coordinator and want to find out how many event rooms you will need to accommodate the event schedules.

Given the event schedule as follows:

{8-9}, {9-10}, {8-10}, {11,14}, {14,15},{13,16}, {10, 13},{10,12}, {13,15}

Event time can not overlap unless one event ends in the same hour as the other event start.
e.g. event 1 {2,3} and even 2 {3-4} can be held in the same event room.

Your program should calculate how many rooms are necessary.


Answer

At a glance, we just need to merge schedules that are not in conflict and return the count of the unique schedules which overlap each other.

We should first avoid examining the schedule out of order in terms of starting time to avoid mistakes of merging wrong schedules, thereby producing the wrong answer.
Sorting the schedules by start time would take O (n log n).

Now, we have schedules sorted by start time. What do we do next?
We need to examine the schedule in order to merge the schedule. Another problem occurs in this case. It can still take O(N^2) if the schedules are not overlapping at all.

For example,  given the sorted schedules: {8-9}, {8-10}, {9-10} , { 10-13}, {10-2}, two approach is possible.

1) We can compare {8-9} with the rest of the schedule to merge, which can take O(N^2).

2) We can create a separate data structure called, Room, to keep the list of rooms holding overlapping events and scan the list of rooms for each next schedule in the list.
    This can take O(MN), where M is the number of required rooms and N is the number of schedules.
    In the worst case, M can be N when all schedules are overlapping each other.
    So, this can also run in O(N^2)

Can we do better? 

When someone as you, "I would like to hold the event from X to Y, do you have a room available?",
you can see the list of events sorted by end time and say whether you can accommodate the event with existing rooms or new rooms.

What could be that magic list?

That's when the MinHeap comes into play. Using the Minheap sorted by the end time, you can keep the earliest ending event at your fingertip.

Accessing the earliest ending event is O(1).

You can either merge the new event with the earliest ending event or add the new event to the heap.
Adding the new element to the heap takes O (log N).

This gives you overall O( N log N) time for scanning and merging the schedule, which is better than
O( N ^2).

Here is the algorithm running in O (N log N). Implementation of MinHeap can be ignored if you already know how to implement the Heap. In the interview, you just tell the interviewer that you will use Min Heap sorted by "end" time of schedule.

	#include <vector>
	#include <math.h>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	struct schedule {
	int start;
	int end;
	schedule(int s, int e): start(s), end(e){}
	};
	class MinHeap{
	public:
	schedule* Extract()
	{
	schedule* result = list[0];
	swap(0, list.size()-1);
	list.pop_back();
	Heapify(0);
	return result;
	}
	void Add(schedule * node)
	{
	list.push_back(node);
	BubbleUp(list.size()-1);
	}
	int size()
	{
	return list.size();
	}
	private:
	void Heapify(int root)
	{
	auto p = root;
	auto l = left(p);
	auto r = right(p);
	if (l < list.size() && !is_parent(p, l))
	p = l;
	if (r <list.size() && !is_parent(p, r))
	p = r;
	if (p != root)
	{
	swap(p, root);
	Heapify(p);
	}
	}
	void BubbleUp(int child)
	{
	if (child == 0)
	return;
	auto p = parent(child);
	if (!is_parent(p, child))
	{
	swap(p, child);
	BubbleUp(p);
	}
	}
	int left(int i) { return (2*i +1);}
	int right(int i) {return (2*i + 2);}
	int parent(int i) { return floor(i/2);}
	bool is_parent(int parent, int child)
	{
	return (list[parent]->end < list[child]->end);
	}
	void swap(int src, int dst)
	{
	auto tmp = list[src];
	list[src] = list[dst];
	list[dst] = tmp;
	}
	vector<schedule *> list;
	};
	bool compare(schedule * prev, schedule * next)
	{
	return prev->start < next->start;
	}
	int count_room(vector<schedule*>& input)
	{
	sort(input.begin(), input.end(), compare);
	MinHeap heap;
	for (int i = 0; i < input.size(); i++)
	{
	if (heap.size() == 0)
	heap.Add(input[i]);
	else
	{
	schedule* min = heap.Extract();
	if (min->end <= input[i]->start)
	{
	min->end = input[i]->end;
	} else {
	heap.Add(input[i]);
	}
	heap.Add(min);
	}
	}
	return heap.size();
	}
	int main()
	{
	// {8-9}, {9-10}, {8-10}, {11,14}, {14,15},{13,16}, {10, 13},{10,12}, {13,15}
	vector<schedule *> input;
	input.push_back(new schedule(8,9));
	input.push_back(new schedule(9,10));
	input.push_back(new schedule(8,10));
	input.push_back(new schedule(11,14));
	input.push_back(new schedule(14,15));
	input.push_back(new schedule(13,16));
	input.push_back(new schedule(10,13));
	input.push_back(new schedule(10,12));
	input.push_back(new schedule(13,15));
	cout<< "rooms required = "<< count_room(input)<<endl;
	return 1;
	}

view raw counting_room.cpp hosted with ❤ by GitHub

UPDATE(2019-07-29): solved the problem again in python. Initially, I thought I can just use the list matrixes to keep track of event booking.

However, I later realized that I can do the optimization of event compaction if I assign the events to the matrixes in a round-robin fashion (there might be a better matrix).

So. fell back to the MinHeap algorithm for optimization.

	def compare(l, r):
	if l[0] < r[0]:
	return -1
	return 1
	class MinHeap:
	def __init__(self):
	self.list = [None]
	def add(self, value):
	self.list.append(value)
	self.bubbleUp(len(self.list) - 1)
	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.bubbleDown(1)
	return value
	def length(self):
	return len(self.list) - 1
	def is_child(self, parent, child):
	#compare end time
	return self.list[parent][1] < self.list[child][1]
	def left(self, p):
	return 2 * p
	def right(self, p):
	return 2 * p + 1
	def parent(self, c):
	return c // 2
	def swap(self, l, r):
	tmp = self.list[l]
	self.list[l] = self.list[r]
	self.list[r] = tmp
	def bubbleUp(self, child):
	if child <= 1:
	return
	parent = self.parent(child)
	if self.is_child(parent, child) != True:
	self.swap(parent, child)
	self.bubbleUp(parent)
	def bubbleDown(self, parent):
	if parent >= len(self.list) - 1:
	return
	left = self.left(parent)
	if left > len(self.list) - 1:
	return
	right = self.right(parent)
	to_swap = left if right > len(self.list) - 1 or self.is_child(left, right) == True else right
	if self.is_child(parent, to_swap) != True:
	self.swap(parent, to_swap)
	self.bubbleDown(to_swap)
	class EventCoordinator:
	def count_required_rooms(self, events):
	#sort events by start time
	sorted_events = sorted(events, cmp = compare)
	heap = MinHeap()
	for event in sorted_events:
	# get room ending earliest
	if heap.length() == 0:
	heap.add(event)
	else:
	room = heap.extract()
	if room[1] <= event[0]:
	#expand room's booked event
	room = [room[0], event[1]]
	else:
	#overlap happens, create a new room
	new_room = [event[0], event[1]]
	heap.add(new_room)
	heap.add(room)
	return heap.length()
	coordinator = EventCoordinator()
	input = [[8,9], [9,10], [8,10], [11,14], [14,15],[13,16], [10, 13],[10,12], [13,15]]
	print("input = {} rooms = {}".format(input, coordinator.count_required_rooms(input)))

view raw amazon_count_event_room_with_heap.py hosted with ❤ by GitHub

Practice statistics
19:57: to write up the code.

made a critical mistake using an unsorted event list in the code.
Need to review the code better !!

UPDATE(2022-06-12): Solved again. Forgot about how to implement the minHeap. Took a while to figure out which algorithm to use for better optimation. Could not finish the coding within the satisfiable time.

	# optional min heap implementation
	class MinHeap:
	def __init__(self):
	self.list=[None]
	def len(self):
	return len(self.list) - 1
	def parent(self, child):
	return child // 2
	def left(self, parent):
	return 2 * parent
	def right(self, parent):
	return 2 * parent + 1
	def is_child(self, parent, child):
	return self.list[parent][1] < self.list[child][1]
	def swap(self, src, target):
	tmp = self.list[src]
	self.list[src] = self.list[target]
	self.list[target] = tmp
	def bubble_down(self, parent):
	if parent >= self.len():
	return
	left = self.left(parent)
	# if there is not left for the parent, stop
	if left >= self.len():
	return
	right = self.right(parent)
	to_swap = left if right >= self.len() or self.is_child(left, right) == True else right
	if self.is_child(parent, to_swap) != True:
	self.swap(parent, to_swap)
	self.bubble_down(to_swap)
	def bubble_up(self, child):
	parent = self.parent(child)
	if parent <= 0:
	return
	if self.is_child(parent, child) != True:
	self.swap(parent, child)
	self.bubble_up(parent)
	def extract(self):
	if self.len() <= 0:
	return None
	min = self.list[1]
	self.swap(1, len(self.list) - 1)
	self.list.pop()
	self.bubble_down(1)
	return min
	def add(self, value):
	self.list.append(value)
	self.bubble_up(len(self.list) - 1)
	# code
	class Scheduler:
	def __init__(self):
	self.heap = MinHeap()
	def find_rooms_for_meetings(self, inputs):
	# sort the input by start time O(n log n)
	inputs.sort(key= lambda i:i[0])
	# add the new events via heap O( n log n)
	for i in inputs:
	# check if the current meeting can bd accomodated.
	available = self.heap.extract() # log N
	if available == None or available[1] > i[0]:
	self.heap.add(i) # log N
	elif available[1] <= i[0]:
	# merge available and current i and put it back to the min heap
	available[0] = min(available[0], i[0])
	available[1] = max(available[1], i[1])
	#put back the available, log N
	if available != None:
	self.heap.add(available) # log N
	return self.heap.len()
	# test
	inputs =[
	[8, 9], [9,10], [8, 10], [11,14], [14,15],[13,16], [10, 13],[10,12], [13,15]
	]
	scheduler = Scheduler()
	num_rooms = scheduler.find_rooms_for_meetings(inputs)
	print ("required rooms = {}".format(num_rooms))

view raw count_meeting_rooms.py hosted with ❤ by GitHub