educative.io

Educative

Count Open: Possibly a much simpler way?

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

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
2 Likes

Can you explain the reasoning behind comparing the starting and ending times? (Your solution seems to work though).

Sure.
The purpose of the comparison is to find out which is event is nearer - the end of a current meeting (end_times[end_idx]) or the start of a new meeting (start_times[start_idx]).
This ensures that all events (meeting starts and ends) are processed in order.
If you implement Minh’s idea it’s even simpler because you have one sorted list with all start/end events already in order.
Hope this helps,
Guy

1 Like

Agree. Mine also maintain maximum open room at a time. Here is my code:

if (meetings.size() <= 1) {
  return meetings.size();
}

Collections.sort(meetings, new Comparator < Meeting > () {
  public int compare(Meeting m1, Meeting m2) {
    int result = m1.start - m2.start;
    if (result != 0) {
      return result;
    } else {
      return m1.end - m2.end;
    }
  }
});

int start = meetings.get(0).start;
int end = meetings.get(0).end;
int room = 1;
int result = 1;
for (int i = 1; i < meetings.size(); i++) {
  Meeting curr = meetings.get(i);
  if (curr.start < end) {
    end = Math.min(end, curr.end);
    room++;
    result = Math.max(room, result);
  } else {
    start = curr.start;
    end = curr.end;
    room = 1;
  }
}

return result;