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.
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.
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 !!
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.
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.
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.
Comments
Post a Comment