Meeting Room II in Javascript
As you know, I have been doing a lot of algorithm questions lately. This week let’s talk about another classic interview question that often comes out: Meeting Room II (Leetcode #253).
A lot of Javascript programmers might encounter difficulty with this type of question. Due to stumbling upon what kind of data structure/algorithm topic to use. The most definitive answer should be the Priority Queue(heap) topic. However, Javascript does not come with a built-in Priority Queue, not like Java, Python, or C++ has built-in Priority Queue. But that’s ok because there are multiple ways of solving this problem.
The other way of solving this problem is using a greedy and two pointers approach.
Intuition
The meeting timings given to us define a chronological order of events throughout the day. With the start and end timings of the intervals, we can define this chronological order.
Arranging the meetings according to their start times helps us know the natural order of meeting throughout the day. Arranging the sessions according to their end-time helps us know when the meeting ends in order throughout the day. This is important because an occupied room from early events has now become free.
We know the meeting defined by the start and end times of the interval. But with these algorithms, we treat the start and end times individually. This doesn’t sound very clear at first, but it works because we know an earlier meeting has ended when there is an ending event. We don’t have to be concerned about which meeting has ended. All we care about is that some of the meetings ended; thus, the room becomes available for the next event to reuse.
Implementation
Let start sorting the meeting duration with start time and create a copy array sort it with the end time. Sorting the end time ascendingly, we can easily get the earliest meeting’s end time. Whenever there is a start meeting, we need to add one room, but before adding rooms, we check to see if any previous meeting ends, which is why we check the start with the first end (starts[i][0]<ends[j][1]). When the start is bigger than the end, we know the previous meeting ends, and we can reuse that room. Then, we compare it with the next meeting with the second end; since the first end is already taken. Repeat until we traverse through the entire interval. Notice the meeting’s start is always smaller than the end of the meeting; if the end is smaller than the start, we know the previous meeting ended, and one of the rooms released for reuse.
Time & Space Complexity
Time complexity should be O(N log N). We are sorting the two arrays (start and end) individually. Each of them contains N elements considering there are N intervals.
Space complexity should be O(N) due to creating two individual arrays of size N, one for keeping track of start times and one for the end times.
There you go, folks, that’s how you solve meeting room II without Priority Queue(heap) in javascript.
Thanks for reading my article. If you enjoyed what you read, consider connecting or dropping me a line at osgood1024@gmail.com.