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

class ConferenceRoom
  attr_accessor :meetings

  def initialize
    self.meetings = []

  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)
          raise "Conference room can't fit all meetings"

  def schedule(meeting)
    self.meetings << meeting

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?

  • 1
    \$\begingroup\$ Quick idea without any code: order the meetings and compare the end date of the first date with the start date of the next. If there is a overlapping you have your result. if not, check the end date of the 2nd with the next start date. \$\endgroup\$
    – knut
    Commented Feb 6, 2016 at 15:29
  • \$\begingroup\$ Yeh I overcomplicated things. Your solution would be O of whatever you use for the sorting algorithm + O(n) to look through each element. Way simpler \$\endgroup\$
    – bigpotato
    Commented Feb 6, 2016 at 15:33

1 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

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.

  • \$\begingroup\$ Nice! each_cons is neat thanks for the tips! \$\endgroup\$
    – bigpotato
    Commented Feb 6, 2016 at 16:10
  • \$\begingroup\$ I should've totally utilized the "freedom" of the question and sorted. Will keep that in mind from now on every time a "list of ..." is the input. \$\endgroup\$
    – bigpotato
    Commented Feb 6, 2016 at 16:11
  • \$\begingroup\$ What would the time complexity? of this be? time needed by sort_by + O(n) ? \$\endgroup\$
    – bigpotato
    Commented Feb 6, 2016 at 16:21
  • \$\begingroup\$ @Edmund Pretty much. I guess each_cons is technically O(n-1) since it iterates pairs, but that doesn't matter much \$\endgroup\$
    – Flambino
    Commented Feb 6, 2016 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.