How hard is LeetCode 253. Meeting Rooms II?

LeetCode 253. Meeting Rooms II is rated Medium on LeetCode.

What is the time complexity of LeetCode 253. Meeting Rooms II?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 253. Meeting Rooms II?

The Python solution on this page uses O(m), where n is the number of meetings and m is the maximum end time auxiliary space.

What topics does LeetCode 253. Meeting Rooms II cover?

LeetCode 253. Meeting Rooms II is tagged Greedy, Array, Two Pointers, Prefix Sum, Sorting and Heap (Priority Queue) on LeetCode.

Is LeetCode 253. Meeting Rooms II a premium problem?

Yes. LeetCode 253. Meeting Rooms II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Meeting Rooms II — LeetCode 253 Python Solution

MediumLeetCode PremiumGreedyArrayTwo PointersPrefix SumSortingHeap (Priority Queue)

Problem: #253
Pattern: Prefix Sum
Reading time: 2 min
Source: leetcode.com

The problem

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example

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

Python solution

Python

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        m = max(e[1] for e in intervals)
        d = [0] * (m + 1)
        for l, r in intervals:
            d[l] += 1
            d[r] -= 1
        ans = s = 0
        for v in d:
            s += v
            ans = max(ans, s)
        return ans

Complexity

Measure	Complexity
Time	O(n + m)
Space	O(m), where n is the number of meetings and m is the maximum end time auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 253. Meeting Rooms II is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

On study lists

This problem is on Blind 75 and NeetCode 150.

Frequently asked questions

How hard is LeetCode 253. Meeting Rooms II?: LeetCode 253. Meeting Rooms II is rated Medium on LeetCode.
What is the time complexity of LeetCode 253. Meeting Rooms II?: The Python solution on this page runs in O(n + m).
What is the space complexity of LeetCode 253. Meeting Rooms II?: The Python solution on this page uses O(m), where n is the number of meetings and m is the maximum end time auxiliary space.
What topics does LeetCode 253. Meeting Rooms II cover?: LeetCode 253. Meeting Rooms II is tagged Greedy, Array, Two Pointers, Prefix Sum, Sorting and Heap (Priority Queue) on LeetCode.
Is LeetCode 253. Meeting Rooms II a premium problem?: Yes. LeetCode 253. Meeting Rooms II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.