Employee Free Time

Clarify the problem

• The problem is to find the free time slots of all employees in a schedule.
• The input is a list of schedules for each employee, where each schedule is a list of intervals representing their working hours.
• The output should be a list of free time slots common to all employees.

Analyze the problem

• We need to find the time slots where no employee is scheduled to work.
• To find the common free time slots, we can merge the intervals of each employee's schedule and then find the gaps between them.

Design an algorithm

• Merge intervals of each employee's schedule:
  • Sort the intervals based on the start time.
  • Initialize an empty list called "merged" to store the merged intervals.
  • Iterate through each interval:
    • If "merged" is empty or the current interval does not overlap with the last merged interval, add the current interval to "merged".
    • Otherwise, update the end time of the last merged interval to be the maximum of the current interval's end time and the last merged interval's end time.
• Find the free time slots:
  • Initialize an empty list called "free_slots".
  • Iterate through the merged intervals:
    • If the next interval's start time is greater than the current interval's end time, it represents a free slot.
      • Add the free slot (current interval's end time to next interval's start time) to "free_slots".

Explain your approach

• First, we will merge the intervals of each employee's schedule to identify the occupied time slots.
• Then, we will iterate through the merged intervals and find the free time slots between them.
• By considering the intervals in sorted order, we can easily determine the gaps where no employee is scheduled.

Write clean and readable code

def employeeFreeTime(schedule):
    merged = mergeIntervals(schedule)
    return findFreeSlots(merged)

def mergeIntervals(schedule):
    merged = []
    schedule.sort(key=lambda x: x[0])  # Sort based on start time
    for interval in schedule:
        if not merged or interval[0] > merged[-1][1]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

def findFreeSlots(merged):
    free_slots = []
    for i in range(1, len(merged)):
        start = merged[i-1][1]
        end = merged[i][0]
        if start < end:
            free_slots.append([start, end])
    return free_slots

Test your code

• Let's test the code with some test cases:

# Test case 1
schedule = [[[1, 3], [6, 7]], [[2, 4]], [[2, 5], [9, 12]]]
# Employee 1: [1, 3], [6, 7]
# Employee 2: [2, 4]
# Employee 3: [2, 5], [9, 12]
# Merged intervals: [1, 5], [6, 7], [9, 12]
# Free slots: [5, 6], [7, 9]
print(employeeFreeTime(schedule))  # Output: [[5, 6], [7, 9]]

# Test case 2
schedule = [[[1, 2], [5, 6]], [[1, 3]], [[4, 10]]]
# Employee 1: [1, 2], [5, 6]
# Employee 2: [1, 3]
# Employee 3: [4, 10]
# Merged intervals: [1, 3], [4, 10]
# Free slots: [3, 4]
print(employeeFreeTime(schedule))  # Output: [[3, 4]]

Optimize if necessary

• The current solution has a time complexity of O(nlogn), where n is the total number of intervals in all employees' schedules. This is because we need to sort the intervals before merging them.
• The space complexity is O(n), where n is the total number of intervals in all employees' schedules. This is because we need to store the merged intervals.

Handle error cases

• The code assumes that the input is a valid list of schedules, where each schedule is a list of intervals. If the input is invalid, the behavior of the code may not be as expected.
• The code does not handle cases where the intervals are not in ascending order or if the end time of an interval is before its start time.

Discuss complexity analysis

• The time complexity of the solution is O(nlogn) because we sort the intervals before merging them. The merging process takes linear time O(n), where n is the total number of intervals.
• The space complexity is O(n) because we need to store the merged intervals, which can be at most the same size as the input.
• The algorithm efficiently finds the free time slots by merging and analyzing the intervals, minimizing unnecessary comparisons and iterations.