"Can a list of meetings all be scheduled in a conference room?"

Question

I was given this question at an interview for a position I just got rejected by, so looking to improve and see what better answers there are!

Input: List of meetings

Output: Can conference room fit all the meetings

It was an open ended problem so I was kinda flustered. My first stab at it was probably too much in terms of set up (he was probably just looking for a solution, not so much for a grasp of object oriented principles) and I think I totally diverged from the Output, but still going to paste my answer anyway:

class Meeting
  attr_accessor :start_time
  attr_accessor :end_time

  def does_not_overlap?(start_time, end_time)
    self.start_time < start_time && self.end_time < end_time ||
    self.start_time > start_time && self.end_time > end_time ||
  end
end

class ConferenceRoom
  attr_accessor :meetings

  def initialize
    self.meetings = []
  end

  def bulk_schedule(list_of_meetings)
    currently_scheduled_meetings = self.meetings
    list_of_meetings.each do |meeting|
      self.meetings.each do |scheduled_meeting|
        if currently_scheduled_meetings.does_not_overlap?(meeting)
          schedule(meeting)
        else
          raise "Conference room can't fit all meetings"
        end
      end
    end
  end

  def schedule(meeting)
    self.meetings << meeting
  end
end

My brute force solution was this, which was just to loop through the array of meetings and see if any of them were scheduled at a certain time range when scheduling new meetings. This runs in \$O(n^2)\$ since I have to loop through an array for each element in another array. When he asked how I would optimize it, I said I would use a hash with the time range as keys and loop through those instead. However, thinking back on this I don't think that would improve things at all.

My friend said to sort the array and do binary search on it. However, I don't get how I would do that given the meetings have 2 properties we have to keep in mind (start time and end time), not just one. Can someone shed some light?

Answer 1

Like knut suggested, a simple solution would be to sort the meetings by start time and for each check if it conflicts with the next.

E.g. given a list of meetings:

conflict = meetings.sort_by(&:start_time).each_cons(2).any? do |a, b|
  a.end_time > b.start_time
end

No need to model a conference room, or raise exceptions; conflict will indicate if the meetings overlap or not.

If the question involved a list of pre-scheduled meetings, and having to check if a new meeting would fit, it'd be a different story. You could use something like this, but the question doesn't call for it.

As for the rest of your code, a few things stood out to me:

• does_not_overlap? is a bit odd

  • it's a negative assertion, rather than overlaps?
  • why not pass in a Meeting instance instead of start and end times?
  • and it's got a syntax error (hanging ||)

• ConferenceRoom should use the attr_accessor you created or at least @meetings – not self.meetings.

• You raise which, yes, is a sort of output, but it's a bit much. All the question needs is a boolean answer.