MediumArraysSortingHeapGreedy

Meeting Rooms II

2 approaches, code in every language

You are given a list of meeting time intervals, each described by a start and an end time. Determine the smallest number of separate rooms required so that no two overlapping meetings ever have to share a room.

A meeting that ends exactly when another begins does not count as an overlap, so those two meetings can safely reuse the same room.

Example 1

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

Output: 2

The [0,30] meeting overlaps both of the others, so a second room is needed while it runs.

Example 2

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

Output: 1

The two meetings never overlap, so a single room is enough.

Constraints

1 ≤ intervals.length ≤ 10^4
0 ≤ start < end ≤ 10^6

Min-Heap of End Times

Process meetings in start order and reuse a room whenever its earliest-finishing meeting is already over.

Loading animation…

Intuition

Sort the meetings by when they start, then walk through them while keeping a min-heap of the end times of meetings that currently occupy rooms. For each new meeting, if the room that frees up soonest (the smallest end time on the heap) is already done by this meeting's start, we reuse it by popping that end time. Either way we push the current meeting's end time. The heap's size at any moment equals the number of rooms in use, and its peak size is the answer.

Algorithm walkthrough

1Sort the intervals by start time.
2Create an empty min-heap that will store the end times of active meetings.
3For each meeting, if the heap is non-empty and its smallest end time is at or before this meeting's start, pop it because that room is now free.
4Push the current meeting's end time onto the heap.
5After processing everything, the number of elements remaining on the heap is the maximum concurrency, which equals the rooms needed.

Implementation

import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[0])
        heap = []
        for start, end in intervals:
            if heap and heap[0] <= start:
                heapq.heappop(heap)
            heapq.heappush(heap, end)
        return len(heap)

Time

O(n log n)

Space

O(n)

Sorting dominates; the heap holds at most n end times.

Sort Starts and Ends Separately

Sort all start times and all end times, then sweep a timeline counting concurrent meetings.

Loading animation…

Intuition

Overlap only cares about how many meetings are running at once, not which meeting is which. So pull all start times into one sorted list and all end times into another. Sweep through the starts; before admitting each start, release every room whose end time has already passed. The running count of occupied rooms rises with each start and falls with each end, and its highest value during the sweep is the number of rooms required.

Algorithm walkthrough

1Extract every start time into one array and every end time into another.
2Sort both arrays independently.
3Walk through the starts with a pointer j into the ends array, both beginning at zero.
4Before counting a new start, advance j past every end time that is at or before that start, decrementing the active-room count for each.
5Increment the count for the current start and track the maximum count seen; that maximum is the answer.

Implementation

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = sorted(i[0] for i in intervals)
        ends = sorted(i[1] for i in intervals)
        rooms = 0
        max_rooms = 0
        j = 0
        for start in starts:
            while j < len(ends) and ends[j] <= start:
                rooms -= 1
                j += 1
            rooms += 1
            max_rooms = max(max_rooms, rooms)
        return max_rooms

Time

O(n log n)

Space

O(n)

Two sorts plus a single linear sweep.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Peak Charging Bay Demand is our own problem on the technique behind Meeting Rooms II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free