Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 3: Employee Free Time (hard)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

class EmployeeInterval:

    def __init__(self, interval, employeeIndex, intervalIndex):
        self.interval = interval  # interval representing employee's working hours
        # index of the list containing working hours of this employee
        self.employeeIndex = employeeIndex
        self.intervalIndex = intervalIndex  # index of the interval in the employee list

    def __lt__(self, other):
        # min heap based on meeting.end
        return self.interval.end < other.interval.end

class Solution:
  def findEmployeeFreeTime(self, schedule):
      result = []
      heap = []
      schedule = [
        [
            EmployeeInterval(employee_int, i, j) for j, employee_int in enumerate(employee_sch)
        ] for i, employee_sch in enumerate(schedule)
      ]

      for
A

Anonymous

· 2 years ago

Solution relies on fact that working times are sorted, but this isn't specified in the problem.

A

Anonymous

· 2 years ago

from heapq import *

#class Interval:
#    def __init__(self, start, end):
#        self.start = start
#        self.end = end

class EmployeeInterval:

    def __init__(self, interval, employeeIndex, intervalIndex):
        self.interval = interval  # interval representing employee's working hours
        # index of the list containing working hours of this employee
        self.employeeIndex = employeeIndex
        self.intervalIndex = intervalIndex  # index of the interval in the employee list

    def __lt__(self, other):
        # min heap based on meeting.end
        return self.interval.start < other.interval.start

class Solution:
  def findEmployeeFreeTime(self, schedule):
    
    def overlap(a, b):
      if a and b:
        return b.start <= a.end 
      return Fal
Show 1 reply
A

Anonymous

· 3 years ago

Please explain with an example

Show 1 reply
A

Anonymous

· 3 years ago

It is incorrect, when the second shirt of one employer is start earlier than the first shift of other employers

Show 1 reply
A

Anonymous

· 4 years ago

There is a way simpler solution. Create a list [True] * 24. Iterate through all the intervals of all employees and set the True to False whenever an employee is not free. At the end, the list will have True only on the intervals that are free for all employees. This solution has O(1) space complexity and O(N) time complexity.

Show 3 replies
A

Anonymous

· 5 years ago

Solution gives incorrect answer. When employee working hours is, for example, [[[1,3], [2,10]], [[3,5], [7,9]]], the output should be nothing since there are no common free interval. However solution gives [5,7] as output.

Show 2 replies
A

Anonymous

· 5 years ago

The simple solution of sorting all employees' working hours in a list on start time and then checking for non overlapping intervals makes sense. The heap sort solution works, but needs a better explanation on why it works.

Reading Progress

0%

Vote for new content