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

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

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?

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.

StackExchange Code Review Q#119093, answer score: 5