Jobs

Interviews

Discussions

Meeting Scheduler

Medium

PayPal

0 views

Topics:

ArraysTwo Pointers

You are given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration. Your task is to find the earliest time slot that both people can have a meeting of the given duration.

Each time slot is represented as an interval [start, end], representing an available time slot from start to end (inclusive).

Return the earliest time slot [start, end] such that both people have availability for a meeting of the given duration. If there is no solution, return an empty list [].

Example 1:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

Example 2:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []

Constraints:

1 <= slots1.length, slots2.length <= 10⁴
slots1[i].length, slots2[i].length == 2
0 <= slots1[i][0] < slots1[i][1] <= 10⁹
0 <= slots2[i][0] < slots2[i][1] <= 10⁹
duration >= 1

Meeting Scheduler

Medium

PayPal

0 views

Topics:

ArraysTwo Pointers

Each time slot is represented as an interval [start, end], representing an available time slot from start to end (inclusive).

Return the earliest time slot [start, end] such that both people have availability for a meeting of the given duration. If there is no solution, return an empty list [].

Example 1:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

Example 2:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []

Constraints:

1 <= slots1.length, slots2.length <= 10⁴
slots1[i].length, slots2[i].length == 2
0 <= slots1[i][0] < slots1[i][1] <= 10⁹
0 <= slots2[i][0] < slots2[i][1] <= 10⁹
duration >= 1

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:

Are the time slots in `slots1` and `slots2` guaranteed to be sorted by start time?
Can the intervals in `slots1` and `slots2` overlap with each other?
Are the start and end times integers representing minutes from the start of the day, or are they in some other unit?
What should I return if the requested `duration` is longer than any single available time slot for either person?
Is `duration` always a positive integer?

Brute Force Solution

Approach

The brute force approach to the meeting scheduler problem involves checking every single possible time slot to see if it works for all attendees. We systematically explore all potential meeting times, regardless of how inefficient it might be. If a time slot works for everyone, we consider it a potential solution.

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

Start by considering the very first possible moment the meeting could begin.
Check if that time works for everyone by looking at each person's availability to make sure they are all free during that time.
If even one person is busy during that proposed time, then this time does not work, so move on.
If everyone is available at that time, save that time as a possible meeting time.
Now, consider the next possible moment the meeting could begin. It might be just a little later, or a larger jump depending on how detailed our search needs to be.
Repeat the process of checking every person's availability at this new proposed meeting time.
Continue checking every possible meeting time until we have considered every single option.
Finally, choose the best meeting time from the saved options, based on some criteria like 'earliest time', or 'longest possible duration'.

Code Implementation

def meeting_scheduler_brute_force(availability, meeting_duration):
    all_possible_slots = []

    # Iterate through all possible start times.
    for start_time in range(0, 1440 - meeting_duration + 1):
        is_slot_available = True

        # Check if the current slot works for all attendees.
        for person_schedule in availability:
            person_available = False
            for available_slot in person_schedule:
                if start_time >= available_slot[0] and start_time + meeting_duration <= available_slot[1]:
                    person_available = True
                    break

            # If even one person is busy, move on.
            if not person_available:
                is_slot_available = False
                break

        # Save the time if everyone is available.
        if is_slot_available:
            all_possible_slots.append(start_time)

    #Choose earliest time
    if not all_possible_slots:
        return None
    else:
        return all_possible_slots[0]

Big(O) Analysis

Time Complexity

O(N * M * K) – Let N be the total possible time slots we need to check, M be the number of attendees, and K be the average number of time intervals each attendee provides. For each of the N possible time slots, we iterate through all M attendees to check their availability. Checking an attendee's availability requires iterating through their K time intervals to see if the proposed time slot conflicts with any of them. Therefore, the total time complexity is O(N * M * K).

Space Complexity

O(1) – The brute force algorithm described iterates through possible meeting times and checks the availability of each person. It saves possible meeting times. The number of saved meeting times is independent of the input size (N) where N is the total number of time slots or the number of attendees. We save only the best meeting time based on the criteria defined, thus, we only need constant extra space to store the current 'best' meeting time candidate. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To efficiently schedule meetings, we focus on finding overlapping time slots. The key is to organize the meeting times to quickly identify common available periods for all attendees. By comparing meeting times in a specific order we can avoid unnecessary checks and quickly find suitable meeting times.

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

First, put all the meeting times from every person together in one big list and sort them from earliest to latest.
Then, go through the sorted list of meeting times step-by-step.
As you go, keep track of the latest ending time you've seen so far.
When you find a meeting time that starts *after* the latest ending time, that means you've found a free time slot that everyone could use.
If there is an overlap, then the latest ending time is changed to the latest of the two meetings and we keep going.
Keep doing this until you've checked all the meeting times. Every time you find a free slot, add it to your list of available meeting times.
Finally, you will have a list of free time slots where a meeting can be scheduled.

Code Implementation

def meeting_scheduler(schedule):
    merged_schedule = []
    for person_schedule in schedule:
        merged_schedule.extend(person_schedule)

    # Sort all meeting times to process chronologically.
    merged_schedule.sort()

    available_slots = []
    latest_end_time = 0

    for meeting_time in merged_schedule:
        start_time, end_time = meeting_time

        # Check for available slots, identifying gaps in the schedule.
        if start_time > latest_end_time:
            available_slots.append((latest_end_time, start_time))

        # Update the latest end time for overlap checks.
        latest_end_time = max(latest_end_time, end_time)

    return available_slots

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the combined list of meeting times from all individuals, where 'n' represents the total number of meetings across all schedules. Sorting algorithms like merge sort or quicksort typically have a time complexity of O(n log n). The subsequent iteration to find free slots is O(n), as we traverse the sorted list once to compare meeting times and update the latest ending time. Since O(n log n) grows faster than O(n), the overall time complexity is O(n log n).

Space Complexity

O(N) – The algorithm gathers all meeting times into one large list. If we denote the total number of meeting times across all people as N, then creating this combined list requires O(N) space. Also, a list of available meeting times is created and populated during the execution, and in the worst-case it could store almost all of the non-overlapping time intervals, hence requiring O(N) space as well. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Both slots1 and slots2 are empty.	Return an empty list, as there are no available time slots for either person.
One of slots1 or slots2 is empty.	Return an empty list, as a meeting requires availability from both people.
duration is zero or negative.	Return an empty list or throw an exception since a meeting duration must be positive.
No overlapping interval of at least duration exists.	Return an empty list when the algorithm iterates and finds no suitable meeting slot.
Large duration that exceeds any possible overlap.	The algorithm will iterate and correctly return an empty list as there is no suitable meeting slot.
Overlapping intervals exist, but none are long enough to accommodate duration.	The algorithm will check the length of each overlapping interval and skip it if shorter than duration.
Input intervals are not sorted.	Sort both slots1 and slots2 by start time before finding overlaps.
Integer overflow if start/end times are very large.	Use appropriate data types (e.g., long) to avoid overflow or check the overflow explicitly before calculations.

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:

Are the time slots in `slots1` and `slots2` guaranteed to be sorted by start time?
Can the intervals in `slots1` and `slots2` overlap with each other?
Are the start and end times integers representing minutes from the start of the day, or are they in some other unit?
What should I return if the requested `duration` is longer than any single available time slot for either person?
Is `duration` always a positive integer?

Brute Force Solution

Approach

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

Start by considering the very first possible moment the meeting could begin.
Check if that time works for everyone by looking at each person's availability to make sure they are all free during that time.
If even one person is busy during that proposed time, then this time does not work, so move on.
If everyone is available at that time, save that time as a possible meeting time.
Now, consider the next possible moment the meeting could begin. It might be just a little later, or a larger jump depending on how detailed our search needs to be.
Repeat the process of checking every person's availability at this new proposed meeting time.
Continue checking every possible meeting time until we have considered every single option.
Finally, choose the best meeting time from the saved options, based on some criteria like 'earliest time', or 'longest possible duration'.

Code Implementation

def meeting_scheduler_brute_force(availability, meeting_duration):
    all_possible_slots = []

    # Iterate through all possible start times.
    for start_time in range(0, 1440 - meeting_duration + 1):
        is_slot_available = True

        # Check if the current slot works for all attendees.
        for person_schedule in availability:
            person_available = False
            for available_slot in person_schedule:
                if start_time >= available_slot[0] and start_time + meeting_duration <= available_slot[1]:
                    person_available = True
                    break

            # If even one person is busy, move on.
            if not person_available:
                is_slot_available = False
                break

        # Save the time if everyone is available.
        if is_slot_available:
            all_possible_slots.append(start_time)

    #Choose earliest time
    if not all_possible_slots:
        return None
    else:
        return all_possible_slots[0]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, put all the meeting times from every person together in one big list and sort them from earliest to latest.
Then, go through the sorted list of meeting times step-by-step.
As you go, keep track of the latest ending time you've seen so far.
When you find a meeting time that starts *after* the latest ending time, that means you've found a free time slot that everyone could use.
If there is an overlap, then the latest ending time is changed to the latest of the two meetings and we keep going.
Keep doing this until you've checked all the meeting times. Every time you find a free slot, add it to your list of available meeting times.
Finally, you will have a list of free time slots where a meeting can be scheduled.

Code Implementation

def meeting_scheduler(schedule):
    merged_schedule = []
    for person_schedule in schedule:
        merged_schedule.extend(person_schedule)

    # Sort all meeting times to process chronologically.
    merged_schedule.sort()

    available_slots = []
    latest_end_time = 0

    for meeting_time in merged_schedule:
        start_time, end_time = meeting_time

        # Check for available slots, identifying gaps in the schedule.
        if start_time > latest_end_time:
            available_slots.append((latest_end_time, start_time))

        # Update the latest end time for overlap checks.
        latest_end_time = max(latest_end_time, end_time)

    return available_slots

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both slots1 and slots2 are empty.	Return an empty list, as there are no available time slots for either person.
One of slots1 or slots2 is empty.	Return an empty list, as a meeting requires availability from both people.
duration is zero or negative.	Return an empty list or throw an exception since a meeting duration must be positive.
No overlapping interval of at least duration exists.	Return an empty list when the algorithm iterates and finds no suitable meeting slot.
Large duration that exceeds any possible overlap.	The algorithm will iterate and correctly return an empty list as there is no suitable meeting slot.
Overlapping intervals exist, but none are long enough to accommodate duration.	The algorithm will check the length of each overlapping interval and skip it if shorter than duration.
Input intervals are not sorted.	Sort both slots1 and slots2 by start time before finding overlaps.
Integer overflow if start/end times are very large.	Use appropriate data types (e.g., long) to avoid overflow or check the overflow explicitly before calculations.