Leetcode - Meeting Rooms II

Question

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), find the minimum number of days required to schedule all meetings without any conflicts.

This is anintervals question.

Idea

• Basically, they want to know the maximum amount of overlapping intervals at any given point in time (we need a room for each meeting during the max overlap time)
• We use 2 input arrays, start times and end times
  • Both are in sorted order
• We use two pointers for the start and end
• We keep a counter for the amount of rooms needed
• If value at start < value at end, increment count by 1 and shift start pointer (is there an overlap?)
• If value at start ≥ value at end, decrement count by 1 and shift end pointer (has a meeting ended?)

Solution

class Solution:
	def minMeetingRooms(self, intervals: List[Interval]) -> int:
		startTimes = [i.start for i in intervals]
		endTimes = [i.end for i in intervals]
		
		startTimes.sort()
		endTimes.sort()
 
		s, e = 0, 0
		res = 0
		count = 0
 
		while s < len(startTimes):
			if startTimes[s]< endTimes[e]:
				count += 1
				s += 1
			else:
				count -= 1
				e += 1
			res = max(res, count)
 
		return res