Jobs

Interviews

Discussions

Meeting Rooms

Easy

Palo Alto Networks

1 view

Topics:

ArraysTwo Pointers

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

Constraints:

0 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i < end_i <= 10⁶

Try coding it in LeetCode

Meeting Rooms

Easy

Palo Alto Networks

1 view

Topics:

ArraysTwo Pointers

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

Constraints:

0 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i < end_i <= 10⁶

Try coding it in LeetCode

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 expected range for the start and end times of the meetings? Can they be negative?
Can the `intervals` array be empty or null? If so, what should the function return?
Can meeting intervals overlap exactly, meaning the end time of one meeting is the same as the start time of another?
Are the meeting intervals guaranteed to be sorted, or do I need to sort them first?
Are the start and end times of each meeting interval always integers?

Brute Force Solution

Approach

Imagine you're checking if a group of people can all attend a meeting without any scheduling conflicts. The brute force method looks at every single possible pair of meetings and checks if they overlap. It does this for all pairs of meetings to see if there are any conflicts.

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

Take the first meeting and compare it with every other meeting on the list.
If you find any overlap, it means those two meetings cannot be scheduled at the same time.
Move on to the second meeting and compare it to every other meeting (except the first, since we already compared that).
Keep doing this, comparing each meeting with every other meeting that comes after it on the list.
If, during all these comparisons, you find even one pair of meetings that overlap, then the answer is no, everyone cannot attend without conflicts. Otherwise, if you get through the entire process without finding any overlaps, then everyone can attend.

Code Implementation

def can_attend_meetings_brute_force(intervals):
    number_of_meetings = len(intervals)

    for first_meeting_index in range(number_of_meetings):
        for second_meeting_index in range(first_meeting_index + 1, number_of_meetings):
            # Iterate through all meeting pairs

            start_time_first_meeting = intervals[first_meeting_index][0]
            end_time_first_meeting = intervals[first_meeting_index][1]
            start_time_second_meeting = intervals[second_meeting_index][0]
            end_time_second_meeting = intervals[second_meeting_index][1]

            # Check for overlap
            if (start_time_first_meeting < end_time_second_meeting and start_time_second_meeting < end_time_first_meeting):
                # If overlap, return immediately

                return False

    # No overlaps found, return True
    return True

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach involves checking every possible pair of meetings for overlap. Given n meetings, the outer loop iterates through each meeting. The inner loop, for each meeting, compares it with the remaining meetings. Therefore, for n meetings, the number of comparisons is proportional to n * (n-1) / 2. This expression simplifies to O(n²), indicating a quadratic time complexity.

Space Complexity

O(1) – The provided brute force approach for checking overlapping meeting times iterates through pairs of meetings. It only uses a few constant space variables for loop indices and comparisons. No additional data structures like arrays, hash maps, or recursion stacks are created. Therefore, the auxiliary space used is independent of the number of meetings (N), resulting in constant space complexity.

Optimal Solution

Approach

To find the minimum number of meeting rooms needed, think about the meetings as events that start and end at certain times. The key idea is to process these events in order of time, tracking how many meetings are happening simultaneously.

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

First, organize all the meeting times by when they start.
Then, consider another organization of these meetings, but this time based on when they end.
Imagine walking through time. As you encounter the start of a meeting, you need a room, so increase the number of rooms in use.
When you encounter the end of a meeting, a room becomes free, so decrease the number of rooms in use.
The highest number of rooms in use at any point during your walk through time represents the total number of meeting rooms needed.

Code Implementation

def min_meeting_rooms(intervals):
    start_times = sorted([interval[0] for interval in intervals])
    end_times = sorted([interval[1] for interval in intervals])

    rooms_in_use = 0
    max_rooms = 0
    start_pointer = 0
    end_pointer = 0

    # Iterate through start and end times.
    while start_pointer < len(intervals):
        # If a meeting starts before the earliest ending meeting.
        if start_times[start_pointer] < end_times[end_pointer]:
            rooms_in_use += 1
            
            #Keep track of the max rooms needed
            max_rooms = max(max_rooms, rooms_in_use)
            start_pointer += 1

        else:
            # Free up a room when a meeting ends.
            rooms_in_use -= 1

            end_pointer += 1

    # The maximum number of meeting rooms used concurrently.
    return max_rooms

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm first sorts the meeting intervals based on their start times, which takes O(n log n) time. Then, it sorts the meeting intervals based on their end times, which also takes O(n log n) time. Iterating through the sorted lists of start and end times involves two separate linear passes, each taking O(n) time. Since sorting dominates the linear iterations, the overall time complexity is O(n log n) + O(n log n) + O(n) + O(n), which simplifies to O(n log n).

Space Complexity

O(N) – The algorithm sorts the start and end times of the meetings. While the explanation doesn't explicitly state the sort method, sorting algorithms generally require extra space. Assuming a sorting algorithm like merge sort is used, the auxiliary space needed would be proportional to the number of meetings, N, where N is the number of meeting intervals in the input. Therefore, the space complexity is O(N) due to the space needed for sorting the start and end times.

Edge Cases

Case	How to Handle
Null or Empty input array	Return true immediately, as there are no meetings to conflict with each other.
Array with only one meeting interval	Return true immediately, as there is only one meeting and no others to conflict with.
Meeting intervals with identical start and end times (zero duration)	The sorting algorithm handles these intervals without issues, and comparisons treat them like any other interval.
Meeting intervals are perfectly overlapping (same start and end times for all)	The sorting will group them, and comparisons during overlap checking will identify the conflicts.
Large number of meeting intervals to test for time complexity (scalability)	Sorting the intervals is O(n log n), and the overlap check is O(n), resulting in O(n log n) overall complexity.
Meeting intervals with start/end times at the integer limits (Integer.MAX_VALUE, Integer.MIN_VALUE)	Ensure comparisons do not result in integer overflow by using appropriate comparison methods or data types.
Meeting intervals are sorted (already in increasing order of start time)	The algorithm should still execute correctly and efficiently, as the sorting step will be quick.
Meeting intervals with same start time but different end times	Sorting will order based on start time, and in case of ties, the language's sort will use a stable algorithm (as guaranteed for java.util.Arrays.sort for object arrays) maintaining original relative order, which should not impact the overlap detection logic.

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 expected range for the start and end times of the meetings? Can they be negative?
Can the `intervals` array be empty or null? If so, what should the function return?
Can meeting intervals overlap exactly, meaning the end time of one meeting is the same as the start time of another?
Are the meeting intervals guaranteed to be sorted, or do I need to sort them first?
Are the start and end times of each meeting interval always integers?

Brute Force Solution

Approach

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

Take the first meeting and compare it with every other meeting on the list.
If you find any overlap, it means those two meetings cannot be scheduled at the same time.
Move on to the second meeting and compare it to every other meeting (except the first, since we already compared that).
Keep doing this, comparing each meeting with every other meeting that comes after it on the list.
If, during all these comparisons, you find even one pair of meetings that overlap, then the answer is no, everyone cannot attend without conflicts. Otherwise, if you get through the entire process without finding any overlaps, then everyone can attend.

Code Implementation

def can_attend_meetings_brute_force(intervals):
    number_of_meetings = len(intervals)

    for first_meeting_index in range(number_of_meetings):
        for second_meeting_index in range(first_meeting_index + 1, number_of_meetings):
            # Iterate through all meeting pairs

            start_time_first_meeting = intervals[first_meeting_index][0]
            end_time_first_meeting = intervals[first_meeting_index][1]
            start_time_second_meeting = intervals[second_meeting_index][0]
            end_time_second_meeting = intervals[second_meeting_index][1]

            # Check for overlap
            if (start_time_first_meeting < end_time_second_meeting and start_time_second_meeting < end_time_first_meeting):
                # If overlap, return immediately

                return False

    # No overlaps found, return True
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, organize all the meeting times by when they start.
Then, consider another organization of these meetings, but this time based on when they end.
Imagine walking through time. As you encounter the start of a meeting, you need a room, so increase the number of rooms in use.
When you encounter the end of a meeting, a room becomes free, so decrease the number of rooms in use.
The highest number of rooms in use at any point during your walk through time represents the total number of meeting rooms needed.

Code Implementation

def min_meeting_rooms(intervals):
    start_times = sorted([interval[0] for interval in intervals])
    end_times = sorted([interval[1] for interval in intervals])

    rooms_in_use = 0
    max_rooms = 0
    start_pointer = 0
    end_pointer = 0

    # Iterate through start and end times.
    while start_pointer < len(intervals):
        # If a meeting starts before the earliest ending meeting.
        if start_times[start_pointer] < end_times[end_pointer]:
            rooms_in_use += 1
            
            #Keep track of the max rooms needed
            max_rooms = max(max_rooms, rooms_in_use)
            start_pointer += 1

        else:
            # Free up a room when a meeting ends.
            rooms_in_use -= 1

            end_pointer += 1

    # The maximum number of meeting rooms used concurrently.
    return max_rooms

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty input array	Return true immediately, as there are no meetings to conflict with each other.
Array with only one meeting interval	Return true immediately, as there is only one meeting and no others to conflict with.
Meeting intervals with identical start and end times (zero duration)	The sorting algorithm handles these intervals without issues, and comparisons treat them like any other interval.
Meeting intervals are perfectly overlapping (same start and end times for all)	The sorting will group them, and comparisons during overlap checking will identify the conflicts.
Large number of meeting intervals to test for time complexity (scalability)	Sorting the intervals is O(n log n), and the overlap check is O(n), resulting in O(n log n) overall complexity.
Meeting intervals with start/end times at the integer limits (Integer.MAX_VALUE, Integer.MIN_VALUE)	Ensure comparisons do not result in integer overflow by using appropriate comparison methods or data types.
Meeting intervals are sorted (already in increasing order of start time)	The algorithm should still execute correctly and efficiently, as the sorting step will be quick.
Meeting intervals with same start time but different end times	Sorting will order based on start time, and in case of ties, the language's sort will use a stable algorithm (as guaranteed for java.util.Arrays.sort for object arrays) maintaining original relative order, which should not impact the overlap detection logic.