3
\$\begingroup\$

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?

\$\endgroup\$
  • 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 Feb 6 '16 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 Feb 6 '16 at 15:33
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice! each_cons is neat thanks for the tips! \$\endgroup\$ – bigpotato Feb 6 '16 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 Feb 6 '16 at 16:11
  • \$\begingroup\$ What would the time complexity? of this be? time needed by sort_by + O(n) ? \$\endgroup\$ – bigpotato Feb 6 '16 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 Feb 6 '16 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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