educative.io

Count Open: Possibly a much simpler way?


#1

We can put all start and end times in 1 giant array, sort them (Put them in an object to know which one is start time, which one is end time)
Then keep a countOpen, and do something similar to matching open, close brackets. return maxCountOpen


#2

I agree!

I did something similar with two arrays: one for meeting start times and another for meeting end times. This makes it possible to get rid of the heap, although the time and space complexities stay the same. Actually if we were using an in-place sort, the space complexity would have improved!

This is my solution:

def min_meeting_rooms(meetings):
  start_times = [m.start for m in meetings]
  end_times = [m.end for m in meetings]
  start_times.sort()
  end_times.sort()

  start_idx = 0
  end_idx = 0
  n_simul = 0
  max_simul = 0
  while start_idx < len(meetings) and end_idx < len(meetings):
    if end_times[end_idx] <= start_times[start_idx]:
      n_simul -= 1
      end_idx += 1
    else:
      n_simul += 1
      max_simul = max(max_simul, n_simul)
      start_idx += 1

  return max_simul