30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 253. Meeting Rooms II

Given a list of meeting time intervals, determine the minimum number of conference rooms required so that no meetings overlap. The core challenge is computing the maximum number of concurrent intervals (e.g., via sorting with a min-heap of end times or a sweep-line of start/end events).

Asked at:

Amazon

Microsoft

Google

DESCRIPTION

Input:


intervals = [[0,30], [5,10], [15,20]]

Output:

Explanation: At time 5, meetings [0,30] and [5,10] overlap. At time 15, meetings [0,30] and [15,20] overlap. Maximum concurrent meetings is 2, so we need 2 rooms.

Constraints:

1 <= intervals.length <= 10^4
0 <= start_i < end_i <= 10^6
Each interval represents a valid meeting time

Understanding the Problem

Let's understand what we're being asked to do. We have a list of meeting time intervals like [[0,30], [5,10], [15,20]], where each interval [start, end] represents a meeting that starts at time start and ends at time end.

We need to determine the minimum number of conference rooms required so that no two meetings overlap in the same room. For example, with [[0,30], [5,10], [15,20]], at time 5 we have two meetings happening simultaneously (the [0,30] meeting and the [5,10] meeting), so we need at least 2 rooms.

Key constraint: Meetings are represented as intervals with start and end times. If one meeting ends exactly when another starts (e.g., [0,10] and [10,20]), they can use the same room (no overlap).

Edge cases to consider: What if all meetings happen at different times (need only 1 room)? What if all meetings overlap completely (need as many rooms as meetings)? What if the intervals list is empty?

Brute Force Approach

The brute force approach checks every pair of meetings to see if they overlap. For each meeting, count how many other meetings it overlaps with. The maximum overlap count plus one gives the minimum rooms needed. This requires comparing every meeting with every other meeting, leading to quadratic time complexity. While simple to understand, this approach becomes impractical for large numbers of meetings.

def min_meeting_rooms(intervals):
    """
    Brute force approach: For each meeting, count how many other meetings
    it overlaps with. The maximum overlap count gives minimum rooms needed.
    Time: O(n^2), Space: O(1)
    """
    if not intervals:
        return 0
    
    max_rooms = 0
    
    # For each meeting, count overlaps with all other meetings
    for i in range(len(intervals)):
        overlap_count = 1  # Count the meeting itself
        
        # Compare with every other meeting
        for j in range(len(intervals)):
            if i != j:
                # Check if meetings overlap
                # Two intervals [a,b] and [c,d] overlap if a < d and c < b
                if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]:
                    overlap_count += 1
        
        # Track maximum overlaps seen
        max_rooms = max(max_rooms, overlap_count)
    
    return max_rooms

Start brute force: count overlaps for each meeting

0 / 46

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) We compare each meeting with every other meeting, resulting in n*(n-1)/2 comparisons, which is O(n²)

Space Complexity: O(1) We only need a constant amount of space to track the maximum overlap count

Building Intuition

The number of rooms needed at any moment equals the number of meetings happening simultaneously at that moment.

The answer is the maximum number of concurrent meetings across all time points. If we track when meetings start and end, we can count how many are active at each moment.

Instead of checking every pair of meetings for overlap (which would be O(n²)), we can process all start and end times in chronological order.

When we encounter a start time, one more room is needed. When we encounter an end time, one room becomes available. The peak concurrent count tells us the minimum rooms required.

Imagine you're managing a building's conference rooms in real-time. You have a counter showing 'Rooms Currently In Use'.

As each meeting starts, increment the counter. As each meeting ends, decrement it. The highest value the counter reaches throughout the day is the minimum number of rooms you need to build.

This is like a 'sweep line' moving through time, tracking the maximum overlap at any point.

Common Mistakes

Forgetting that meetings ending exactly when another starts don't overlap - use < not <= when comparing end times with start times

Not handling the case where multiple events happen at the same time - process all end events before start events at the same timestamp

In the heap approach, forgetting to remove ALL ended meetings before adding a new one, not just the earliest one

Confusing the heap size with the answer - the maximum heap size seen is the answer, not the final heap size

Off-by-one errors when counting concurrent meetings - make sure to track the maximum count correctly as you process events

Optimal Solution

The optimal approach uses a sweep-line algorithm with event processing. Separate all start and end times into events, then sort them chronologically. Process events in order: increment a counter for each start event, decrement for each end event. Track the maximum counter value reached, which represents the peak number of concurrent meetings. Alternatively, use a min-heap to track meeting end times: sort meetings by start time, and for each meeting, remove all ended meetings from the heap before adding the current meeting's end time. The heap size represents rooms needed.

def min_meeting_rooms(intervals):
    """
    Find minimum number of conference rooms required.
    Uses sweep-line algorithm with start/end events.
    """
    # Handle edge case
    if not intervals:
        return 0
    
    # Create events: (time, type) where type=1 for start, type=-1 for end
    events = []
    
    # Build events list from intervals
    for start, end in intervals:
        events.append((start, 1))  # Meeting starts, need +1 room
        events.append((end, -1))   # Meeting ends, free -1 room
    
    # Sort events by time (if same time, process ends before starts)
    events.sort(key=lambda x: (x[0], x[1]))
    
    # Track current rooms in use and maximum rooms needed
    current_rooms = 0
    max_rooms = 0
    
    # Process each event in chronological order
    for time, event_type in events:
        # Update current room count
        current_rooms += event_type
        
        # Track maximum concurrent meetings
        max_rooms = max(max_rooms, current_rooms)
    
    return max_rooms

Start: Find minimum meeting rooms using sweep-line algorithm

0 / 25

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log n) Sorting the events (or meetings) takes O(n log n) time. Processing events or maintaining the heap takes O(n log n) in total. The sorting step dominates.

Space Complexity: O(n) We need O(n) space to store the events or the heap, which in the worst case contains all meeting end times

What We've Learned

Min-heap for tracking active intervals: When dealing with overlapping intervals, use a min-heap to track end times of ongoing events - this allows O(log n) insertion/removal to efficiently determine when resources become available, making it perfect for scheduling and resource allocation problems.
Sweep-line algorithm pattern: Transform interval problems into point events (start/end) and process them chronologically - this converts a 2D interval problem into a 1D timeline problem where you track the current count of active intervals at each event.
Sort by start time first: Always sort intervals by start time as your first step - this ensures you process meetings in chronological order and can make greedy decisions about room allocation without missing earlier conflicts.
Heap size equals resource count: The maximum heap size during processing directly represents the answer - when a new meeting starts, add its end time to the heap; when the earliest ending meeting finishes (heap top ≤ current start), reuse that room by popping and pushing the new end time.
Two-pointer event processing: An alternative to heaps is creating separate sorted arrays of start and end times, then using two pointers to track when meetings begin vs. end - increment room count on starts, decrement on ends, tracking the maximum concurrent count.
Real-world resource scheduling: This pattern applies to any resource allocation problem - CPU scheduling, airport runway management, classroom scheduling, or server request handling - wherever you need to determine minimum resources to handle overlapping demands without conflicts.

Test Your Understanding

Why is intervals the right data structure for this problem?

intervals provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early October, 2025

Google

Mid-level

Early September, 2025

Amazon

Junior

Mid August, 2025

Apple

Senior

Get Premium to View All 10+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 253. Meeting Rooms II

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact