# “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 ||
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?

• 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. – knut Feb 6 '16 at 15:29
• 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 – bigpotato Feb 6 '16 at 15:33

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.

• Nice! each_cons is neat thanks for the tips! – bigpotato Feb 6 '16 at 16:10
• 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. – bigpotato Feb 6 '16 at 16:11
• What would the time complexity? of this be? time needed by sort_by + O(n) ? – bigpotato Feb 6 '16 at 16:21
• @Edmund Pretty much. I guess each_cons is technically O(n-1) since it iterates pairs, but that doesn't matter much – Flambino Feb 6 '16 at 16:24