As you prepare for coding interviews, especially those at major tech companies like FAANG (Facebook, Amazon, Apple, Netflix, Google), you’ll encounter various problem-solving techniques. One such approach that frequently appears in interview questions is the “Meeting Room” problem. This article will delve into when and how to use the Meeting Room approach, its applications, and how it can help you ace your coding interviews.

What is the Meeting Room Approach?

The Meeting Room approach is a problem-solving technique used to handle scheduling conflicts or overlapping intervals. It’s typically applied to problems involving time management, resource allocation, or any scenario where you need to determine if a set of intervals overlap or how many non-overlapping intervals can be accommodated.

This approach is named after a common interview question: “Given a list of meeting time intervals, determine if a person can attend all meetings.” The core idea is to efficiently manage and analyze time intervals to make decisions about scheduling or resource allocation.

When to Use the Meeting Room Approach

The Meeting Room approach is particularly useful in the following scenarios:

  1. Interval Scheduling: When you need to determine the maximum number of non-overlapping intervals or activities that can be scheduled.
  2. Conflict Detection: To check if there are any overlapping intervals in a given set.
  3. Resource Allocation: When you need to allocate resources (like meeting rooms) based on time intervals.
  4. Time Management: For problems involving efficient management of time slots or schedules.
  5. Event Planning: To organize events or activities without time conflicts.

Common Interview Questions Using the Meeting Room Approach

Here are some typical interview questions where the Meeting Room approach can be applied:

  1. Given a list of time intervals for meetings, determine if a person can attend all meetings.
  2. Find the minimum number of meeting rooms required to hold all meetings.
  3. Merge overlapping intervals in a list of time intervals.
  4. Find the maximum number of non-overlapping intervals.
  5. Determine if two people’s schedules have any common free time slots.

Implementing the Meeting Room Approach

Let’s look at how to implement the Meeting Room approach for a common interview question: “Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…], determine if a person could attend all meetings.”

Here’s a Python implementation:

def can_attend_meetings(intervals):
    # Sort the intervals based on start time
    intervals.sort(key=lambda x: x[0])
    
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:
            return False
    
    return True

# Test the function
meetings = [[0,30],[5,10],[15,20]]
print(can_attend_meetings(meetings))  # Output: False

meetings = [[7,10],[2,4]]
print(can_attend_meetings(meetings))  # Output: True

In this implementation:

  1. We first sort the intervals based on their start times. This allows us to compare adjacent intervals efficiently.
  2. We then iterate through the sorted intervals, comparing each interval’s start time with the previous interval’s end time.
  3. If we find any overlap (i.e., if the start time of the current interval is less than the end time of the previous interval), we return False, indicating that the person cannot attend all meetings.
  4. If we complete the iteration without finding any overlaps, we return True, indicating that all meetings can be attended.

Time and Space Complexity

For the above implementation:

  • Time Complexity: O(n log n), where n is the number of intervals. This is due to the sorting step, which typically uses a comparison-based sorting algorithm.
  • Space Complexity: O(1) if we’re allowed to modify the input array, or O(n) if we need to create a copy of the input for sorting.

Variations of the Meeting Room Problem

Let’s explore some variations of the Meeting Room problem and how to approach them:

1. Minimum Number of Meeting Rooms

Problem: Given a list of meeting time intervals, find the minimum number of meeting rooms required.

Approach: Use a min-heap to keep track of end times of meetings in progress.

import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    
    # Sort intervals by start time
    intervals.sort(key=lambda x: x[0])
    
    # Use a min heap to track end times of meetings in progress
    rooms = []
    heapq.heappush(rooms, intervals[0][1])
    
    for i in range(1, len(intervals)):
        # If the earliest ending meeting has ended, remove it
        if rooms[0] <= intervals[i][0]:
            heapq.heappop(rooms)
        
        # Add the current meeting's end time
        heapq.heappush(rooms, intervals[i][1])
    
    return len(rooms)

# Test the function
meetings = [[0,30],[5,10],[15,20]]
print(min_meeting_rooms(meetings))  # Output: 2

2. Merge Overlapping Intervals

Problem: Given a collection of intervals, merge all overlapping intervals.

Approach: Sort intervals by start time and then merge overlapping intervals.

def merge_intervals(intervals):
    # Sort intervals based on start time
    intervals.sort(key=lambda x: x[0])
    
    merged = []
    for interval in intervals:
        # If merged is empty or if current interval doesn't overlap with previous
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # Update the end time of the previous interval if necessary
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    return merged

# Test the function
intervals = [[1,3],[2,6],[8,10],[15,18]]
print(merge_intervals(intervals))  # Output: [[1,6],[8,10],[15,18]]

Advanced Applications of the Meeting Room Approach

The Meeting Room approach isn’t limited to just scheduling meetings. Its principles can be applied to various real-world scenarios and more complex coding problems. Let’s explore some advanced applications:

1. Task Scheduling in Operating Systems

In operating systems, the Meeting Room approach can be used to schedule tasks or processes. Each task can be represented as an interval with a start time and duration. The goal is to efficiently allocate CPU time to these tasks while avoiding conflicts.

def schedule_tasks(tasks):
    # Sort tasks based on start time
    tasks.sort(key=lambda x: x[0])
    
    schedule = []
    current_time = 0
    
    for task in tasks:
        start_time, duration = task
        if start_time >= current_time:
            schedule.append(task)
            current_time = start_time + duration
    
    return schedule

# Test the function
tasks = [(1, 4), (3, 2), (4, 1), (5, 3), (6, 2)]
print(schedule_tasks(tasks))  # Output: [(1, 4), (5, 3)]

2. Network Packet Scheduling

In computer networks, the Meeting Room approach can be applied to schedule network packets. Each packet can be represented as an interval with an arrival time and transmission duration. The goal is to maximize throughput while minimizing conflicts.

import heapq

def schedule_packets(packets):
    # Sort packets based on arrival time
    packets.sort(key=lambda x: x[0])
    
    schedule = []
    end_times = []
    
    for packet in packets:
        arrival_time, duration = packet
        
        # Remove packets that have finished transmission
        while end_times and end_times[0] <= arrival_time:
            heapq.heappop(end_times)
        
        # Schedule the packet if there's an available slot
        if len(end_times) < MAX_CONCURRENT_PACKETS:
            schedule.append(packet)
            heapq.heappush(end_times, arrival_time + duration)
    
    return schedule

# Test the function
MAX_CONCURRENT_PACKETS = 2
packets = [(1, 3), (2, 2), (3, 1), (4, 2), (5, 1)]
print(schedule_packets(packets))  # Output: [(1, 3), (2, 2), (4, 2), (5, 1)]

3. Hotel Booking System

The Meeting Room approach can be used to implement a hotel booking system. Each booking can be represented as an interval with check-in and check-out dates. The system needs to determine if a new booking can be accommodated based on room availability.

def can_accommodate_booking(bookings, new_booking):
    # Add the new booking to the list
    all_bookings = bookings + [new_booking]
    
    # Sort bookings based on check-in date
    all_bookings.sort(key=lambda x: x[0])
    
    rooms_occupied = 0
    max_rooms_occupied = 0
    
    events = []
    for check_in, check_out in all_bookings:
        events.append((check_in, 1))  # 1 for check-in
        events.append((check_out, -1))  # -1 for check-out
    
    events.sort()
    
    for date, event_type in events:
        rooms_occupied += event_type
        max_rooms_occupied = max(max_rooms_occupied, rooms_occupied)
    
    return max_rooms_occupied <= TOTAL_ROOMS

# Test the function
TOTAL_ROOMS = 3
bookings = [(1, 3), (2, 4), (4, 5)]
new_booking = (2, 3)
print(can_accommodate_booking(bookings, new_booking))  # Output: True

Common Mistakes and How to Avoid Them

When applying the Meeting Room approach, there are several common mistakes that interviewees often make. Being aware of these pitfalls can help you avoid them and improve your problem-solving skills:

1. Forgetting to Sort Intervals

One of the most common mistakes is forgetting to sort the intervals before processing them. Sorting is crucial for most Meeting Room problems as it allows you to process the intervals in a logical order.

How to avoid: Always start by sorting the intervals based on their start times, unless the problem explicitly states that the intervals are already sorted.

2. Incorrect Comparison of Intervals

Another frequent mistake is comparing intervals incorrectly, especially when checking for overlaps.

How to avoid: Be clear about what constitutes an overlap. Generally, two intervals [a, b] and [c, d] overlap if and only if c < b and a < d.

3. Not Considering Edge Cases

Failing to consider edge cases can lead to incorrect solutions. Common edge cases include empty input, single interval, or intervals with the same start or end times.

How to avoid: Always test your solution with edge cases. Consider inputs like [], [[1,2]], [[1,2], [2,3]], etc.

4. Inefficient Data Structures

Using inefficient data structures can lead to suboptimal solutions. For example, using a list instead of a heap for tracking end times in the “Minimum Meeting Rooms” problem.

How to avoid: Consider the operations you need to perform frequently (e.g., finding the minimum, inserting, deleting) and choose the most appropriate data structure.

5. Misunderstanding the Problem Requirements

Sometimes, interviewees misinterpret what the question is asking, leading to an incorrect approach.

How to avoid: Always clarify the problem requirements with your interviewer. Don’t hesitate to ask questions if anything is unclear.

Practice Problems

To help you master the Meeting Room approach, here are some practice problems you can work on:

  1. Employee Free Time: Given the schedule of multiple employees, find the common free time slots.
  2. Meeting Scheduler: Design a system to schedule meetings efficiently, considering multiple meeting rooms and priorities.
  3. Interval List Intersections: Given two lists of closed intervals, find the intersection of these two interval lists.
  4. Maximum CPU Load: Given a list of jobs with start time, end time, and CPU load, find the maximum CPU load at any time.
  5. Minimum Platforms: Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits.

Conclusion

The Meeting Room approach is a powerful technique for solving a wide range of interval-based problems. It’s particularly useful in scenarios involving time management, resource allocation, and scheduling. By mastering this approach, you’ll be well-equipped to tackle many common coding interview questions, especially those asked by major tech companies.

Remember, the key to success with the Meeting Room approach lies in:

  • Properly sorting the intervals
  • Efficiently comparing and processing intervals
  • Choosing the right data structures for the specific problem
  • Considering all edge cases
  • Understanding the problem requirements thoroughly

As you practice more problems using this approach, you’ll develop a intuition for when and how to apply it effectively. Keep coding, keep practicing, and you’ll be well on your way to mastering this important algorithmic technique!