Jobs

Interviews

Discussions

Employee Free Time

Hard

Snap

3 views

Topics:

ArraysGreedy AlgorithmsSorting

We are given a list of employees, each with a list of non-overlapping interval representing their working time. Each employee's working time list is sorted.

Return the list of finite intervals representing common, positive-length free time for all employees.

You may return the result in any order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [[3,4]].

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

Constraints:

1 <= schedule.length , schedule[i].length <= 50
0 <= schedule[i].start < schedule[i].end <= 10⁸

Employee Free Time

Hard

Snap

3 views

Topics:

ArraysGreedy AlgorithmsSorting

We are given a list of employees, each with a list of non-overlapping interval representing their working time. Each employee's working time list is sorted.

Return the list of finite intervals representing common, positive-length free time for all employees.

You may return the result in any order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [[3,4]].

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

Constraints:

1 <= schedule.length , schedule[i].length <= 50
0 <= schedule[i].start < schedule[i].end <= 10⁸

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the format of the input 'intervals'? Specifically, what data type represents each interval (e.g., tuple, object with start/end properties), and what data types are the start and end times (e.g., integers, floats, timestamps)?
Are the intervals within each employee's schedule guaranteed to be sorted by start time? Are the employee schedules themselves sorted in any particular way?
Can intervals overlap within an employee's schedule, and if so, how should overlapping intervals be handled when determining free time?
If there is no common free time across all employees, what should the output be? Should I return an empty list, or a list with a single interval spanning the entire considered time range?
Are the start and end times inclusive or exclusive? For example, if one interval ends at 10 and another starts at 10, is that considered free time between them?

Brute Force Solution

Approach

The brute force approach to finding employee free time is like checking every single possible time slot to see if everyone is busy. We need to exhaustively compare each employee's work schedule with every other employee's work schedule to find the gaps where no one is working.

Here's how the algorithm would work step-by-step:

First, take all the work schedules from every employee and put them into one big list.
Then, for every possible time slot (imagine dividing the whole day into tiny chunks), check if any employee is working during that specific time.
If no employee is working during that time slot, mark it as a potential free time slot.
Repeat this checking process for every single time slot throughout the entire day or timeframe.
Finally, look at all the potential free time slots you've marked and combine any that are next to each other to create larger blocks of free time.

Code Implementation

def employee_free_time_brute_force(schedules):
    all_intervals = []
    for employee_schedule in schedules:
        all_intervals.extend(employee_schedule)

    # Sort intervals to easily find overlaps and gaps
    all_intervals.sort(key=lambda interval: interval[0])

    free_intervals = []
    if not all_intervals:
        return free_intervals

    current_time = 0
    end_of_previous_interval = all_intervals[0][0]

    for interval in all_intervals:
        start_time = interval[0]
        end_time = interval[1]

        # Check for gaps between previous interval and current interval
        if start_time > end_of_previous_interval:
            free_intervals.append([end_of_previous_interval, start_time])

        #Update the end time of previous interval
        end_of_previous_interval = max(end_of_previous_interval, end_time)

    return free_intervals

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m*log(n*m)) – Let n be the number of employees and m be the average number of intervals per employee. The first step involves merging all employee schedules into a single sorted list. This involves a total of n*m intervals. Sorting this combined list of n*m intervals using an efficient sorting algorithm (like merge sort or quicksort) takes O(n*m*log(n*m)) time. The subsequent step of iterating through the sorted intervals to find the gaps takes O(n*m) time, which is dominated by the initial sorting. Therefore, the overall time complexity is O(n*m*log(n*m)).

Space Complexity

O(N) – The brute force approach described creates a single large list by combining all the work schedules from every employee. In the worst-case scenario, where N is the total number of intervals across all employees' schedules, this list would have N elements. Therefore, the auxiliary space used is proportional to the total number of intervals. The other operations such as comparing time slots do not contribute significantly to the space complexity.

Optimal Solution

Approach

The most efficient approach to finding employee free time involves merging all employee schedules into one sorted timeline. Then, we simply identify the gaps in this unified timeline to find the free time slots. This avoids pairwise comparisons between employees, significantly reducing the work needed.

Here's how the algorithm would work step-by-step:

First, take all the time intervals from all the employees and put them into one big list.
Sort this list of time intervals based on when they start.
Now, walk through the sorted list. Keep track of the latest time anyone is busy.
Whenever you find an interval that starts after the latest busy time, that means there's a free time slot. Record that free time slot.
As you move along, update the latest busy time to be the end of the current interval if it's later than the current latest busy time.
Continue until you've looked at all the time intervals. The free time slots you recorded are the answer.

Code Implementation

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

def employee_free_time(schedules):
    merged_schedule = []
    for employee_schedule in schedules:
        merged_schedule.extend(employee_schedule)

    # Sort the intervals by start time.
    merged_schedule.sort(key=lambda interval: interval.start)

    available_time_slots = []
    latest_busy_time = merged_schedule[0].end

    for interval in merged_schedule[1:]:
        # If the current interval starts after the latest busy time,
        # there's a free time slot.
        if interval.start > latest_busy_time:

            available_time_slots.append(Interval(latest_busy_time, interval.start))

        # Update the latest busy time if the current interval extends it.
        latest_busy_time = max(latest_busy_time, interval.end)

    return available_time_slots

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm's time complexity is dominated by two main operations. First, collecting all intervals into a single list takes O(1) time per interval. Assuming there are 'n' total intervals across all employees, this gathering step is O(n). Second, the sorting of this combined list of intervals takes O(n log n) time using an efficient sorting algorithm like merge sort or heap sort. The final iteration to identify free time slots takes O(n) time as it iterates through the sorted intervals once. Therefore, the overall time complexity is O(n) + O(n log n) + O(n), which simplifies to O(n log n).

Space Complexity

O(N) – The algorithm creates a new list to store all the time intervals from all employees. Let N be the total number of time intervals across all employees. This list has a size proportional to N. The algorithm also keeps track of the latest busy time using a single variable, which is constant space. Thus the auxiliary space is dominated by the sorted list of time intervals, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Input schedule is null or empty	Return an empty list of intervals because there are no employee schedules to process.
Individual employee schedule is null or empty	Treat an empty employee schedule as if the employee is always available, effectively ignoring it for free time calculation.
Overlapping intervals within a single employee's schedule	Merge overlapping intervals for each employee's schedule before considering free time.
Large number of employees with many intervals each	Ensure the chosen algorithm scales efficiently, considering space and time complexity for merging all intervals.
Employee schedules contain adjacent intervals (e.g., [1,2],[2,3])	Ensure adjacent intervals are not mistakenly identified as free time; handle them correctly during the merging process.
All employees have completely overlapping schedules (no free time)	Return an empty list indicating there is no free time available for all employees.
Intervals with very large start and end times leading to potential integer overflow	Use data types that can accommodate large time values, such as long, to prevent overflow issues.
Intervals are not sorted within each employee's schedule	Sort each employee's schedule by start time before processing to ensure proper interval merging and free time identification.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the format of the input 'intervals'? Specifically, what data type represents each interval (e.g., tuple, object with start/end properties), and what data types are the start and end times (e.g., integers, floats, timestamps)?
Are the intervals within each employee's schedule guaranteed to be sorted by start time? Are the employee schedules themselves sorted in any particular way?
Can intervals overlap within an employee's schedule, and if so, how should overlapping intervals be handled when determining free time?
If there is no common free time across all employees, what should the output be? Should I return an empty list, or a list with a single interval spanning the entire considered time range?
Are the start and end times inclusive or exclusive? For example, if one interval ends at 10 and another starts at 10, is that considered free time between them?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, take all the work schedules from every employee and put them into one big list.
Then, for every possible time slot (imagine dividing the whole day into tiny chunks), check if any employee is working during that specific time.
If no employee is working during that time slot, mark it as a potential free time slot.
Repeat this checking process for every single time slot throughout the entire day or timeframe.
Finally, look at all the potential free time slots you've marked and combine any that are next to each other to create larger blocks of free time.

Code Implementation

def employee_free_time_brute_force(schedules):
    all_intervals = []
    for employee_schedule in schedules:
        all_intervals.extend(employee_schedule)

    # Sort intervals to easily find overlaps and gaps
    all_intervals.sort(key=lambda interval: interval[0])

    free_intervals = []
    if not all_intervals:
        return free_intervals

    current_time = 0
    end_of_previous_interval = all_intervals[0][0]

    for interval in all_intervals:
        start_time = interval[0]
        end_time = interval[1]

        # Check for gaps between previous interval and current interval
        if start_time > end_of_previous_interval:
            free_intervals.append([end_of_previous_interval, start_time])

        #Update the end time of previous interval
        end_of_previous_interval = max(end_of_previous_interval, end_time)

    return free_intervals

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, take all the time intervals from all the employees and put them into one big list.
Sort this list of time intervals based on when they start.
Now, walk through the sorted list. Keep track of the latest time anyone is busy.
Whenever you find an interval that starts after the latest busy time, that means there's a free time slot. Record that free time slot.
As you move along, update the latest busy time to be the end of the current interval if it's later than the current latest busy time.
Continue until you've looked at all the time intervals. The free time slots you recorded are the answer.

Code Implementation

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

def employee_free_time(schedules):
    merged_schedule = []
    for employee_schedule in schedules:
        merged_schedule.extend(employee_schedule)

    # Sort the intervals by start time.
    merged_schedule.sort(key=lambda interval: interval.start)

    available_time_slots = []
    latest_busy_time = merged_schedule[0].end

    for interval in merged_schedule[1:]:
        # If the current interval starts after the latest busy time,
        # there's a free time slot.
        if interval.start > latest_busy_time:

            available_time_slots.append(Interval(latest_busy_time, interval.start))

        # Update the latest busy time if the current interval extends it.
        latest_busy_time = max(latest_busy_time, interval.end)

    return available_time_slots

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input schedule is null or empty	Return an empty list of intervals because there are no employee schedules to process.
Individual employee schedule is null or empty	Treat an empty employee schedule as if the employee is always available, effectively ignoring it for free time calculation.
Overlapping intervals within a single employee's schedule	Merge overlapping intervals for each employee's schedule before considering free time.
Large number of employees with many intervals each	Ensure the chosen algorithm scales efficiently, considering space and time complexity for merging all intervals.
Employee schedules contain adjacent intervals (e.g., [1,2],[2,3])	Ensure adjacent intervals are not mistakenly identified as free time; handle them correctly during the merging process.
All employees have completely overlapping schedules (no free time)	Return an empty list indicating there is no free time available for all employees.
Intervals with very large start and end times leading to potential integer overflow	Use data types that can accommodate large time values, such as long, to prevent overflow issues.
Intervals are not sorted within each employee's schedule	Sort each employee's schedule by start time before processing to ensure proper interval merging and free time identification.