Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 3: Employee Free Time (hard)

Problem Statement

For ‘K’ employees, we are given a list of intervals representing each employee’s working hours. Our goal is to determine if there is a free interval which is common to all employees.

Example 1:

Input: Employee Working Hours=[[[1,3], [5,6]], [[2,3], [6,8]]]
Output: [3,5]
Explanation: All the employees are free between [3,5].

Example 2:

Input: Employee Working Hours=[[[1,3], [9,12]], [[2,4]], [[6,8]]]
Output: [4,6], [8,9]
Explanation: All employees are free between [4,6] and [8,9].

Example 3:

.....

.....

.....

Like the course? Get enrolled and start learning!
R

Russell Rogers

· 4 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.

M

Mike Xu

· 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 4 replies
P

Pete Stenger

· 2 years ago

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

D

Daniel Lee

· 4 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
Anh-Quan Cao

Anh-Quan Cao

· 2 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
Manoj Dixit

Manoj Dixit

· 2 years ago

Please explain with an example

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

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

Pete Stenger

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

David Murga

· a year ago

The following example returns [5,7] [[[1,3]], [[2,4]], [[3,5], [7,9]]]

Which assumes employee 1 and 2 are around as long as employee 3. If all employees are free as long as they're not working, then the answer should return

[5,7], [9, 12 / some end time]

The question doesn't specifically state it, but it assumes employees are around until the last employee is, which should be clarified in the question