Skip to content

Volume ITechnology

4.27.5 — Meeting Rooms II ​

LeetCode 253 · Medium

The problem ​

Return the minimum number of rooms needed so that every meeting can happen.

Restating the Problem: You are given a list of meetings with start and end times. If two meetings overlap, they must be put into different rooms. You want to find out the absolute minimum number of rooms required to accommodate all meetings simultaneously.

  • Constraints to note: The number of meetings can be up to 10^4. O(n \log n) sorting approaches are ideal.
  • Edge cases: No meetings (returns 0). Meetings that end exactly when another begins (e.g., [1, 2] and [2, 3]) do not conflict and can share a room.
[[0,30],[5,10],[15,20]]   →  2
[[7,10],[2,4]]            →  1

The brute force, and where it wastes work ​

The naive approach is to use a list of "rooms" where each room contains a list of meetings it hosts. For every new meeting, you check each existing room to see if it can fit without overlapping. If it fits, you place it there; if it overlaps with all existing rooms, you create a new room. This takes O(n^2) time in the worst case (when all meetings overlap, you check O(n) rooms for each of the n meetings). This is too slow for large n.

The pattern ​

The answer is the largest number of meetings happening at the same moment. You need one room per concurrent meeting, and no more, because a room is reusable the instant a meeting ends.

So the question becomes: what is the maximum overlap at any point in time?

There are two standard answers, and you should know both.

Solution 1 — the sweep line ​

Forget which start belongs to which end. Treat starts and ends as separate events, sort all of them by time, and sweep:

  • a start adds one to the count of rooms in use;
  • an end subtracts one.

The answer is the highest the count ever reaches.

python
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = sorted(i[0] for i in intervals)  # (1)
        ends = sorted(i[1] for i in intervals)  # (2)

        rooms = best = 0  # (3)
        s = e = 0  # (4)

        while s < len(starts):  # (5)
            if starts[s] < ends[e]:          # (6) a meeting begins before any ends
                rooms += 1
                s += 1
                best = max(best, rooms)  # (7)
            else:                            # (8) a meeting ends first — free a room
                rooms -= 1
                e += 1

        return best
ts
function minMeetingRooms(intervals: number[][]): number {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);  // (1)
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);  // (2)

  let rooms = 0, best = 0, s = 0, e = 0;  // (3)

  while (s < starts.length) {  // (5)
    if (starts[s] < ends[e]) { rooms++; s++; best = Math.max(best, rooms); }  // (6)
    else { rooms--; e++; }  // (8)
  }

  return best;
}

Separating the starts from the ends is the key move. It looks wrong, because you have thrown away which end belongs to which start. But that does not matter. You are only counting how many meetings are open at each moment, and for that the pairing is irrelevant.

starts[s] < ends[e] uses <, so a meeting ending exactly when another starts frees the room in time. That is the same convention as 4.27.4.

Line by line.

(1) All the start times, sorted.

(2) All the end times, sorted separately. We no longer know which end belongs to which start, and we do not need to. We only count how many meetings are running at each moment.

(3) rooms is how many meetings are running right now, and best is the most that were ever running at once.

(4) A pointer into each list.

(5) Keep going while some meeting has yet to start.

(6) The next thing to happen is a meeting starting, because the next start comes before the next end. One more room is busy. Using < means that when a meeting ends at the very moment another starts, the end is handled first, so the room is reused.

(7) Keep the highest count seen. That is the number of rooms needed.

(8) Otherwise the next thing to happen is a meeting ending. A room is freed.

The loop runs while starts remain. Once every meeting has begun, the count can only fall, so the maximum has already been seen.

Trace for Sweep Line ​

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

  • starts: [0, 5, 15]
  • ends: [10, 20, 30]
s ptr (start val)e ptr (end val)Actionroomsbest
0 (0)0 (10)0 < 10 → start meeting11
1 (5)0 (10)5 < 10 → start meeting22
2 (15)0 (10)15 >= 10 → end meeting12
2 (15)1 (20)15 < 20 → start meeting22
3 (out of bounds)Loop ends2

Answer is 2 ✓.

O(n \log n) time, O(n) space.

Solution 2 — a min-heap of end times ​

Sort the meetings by start. Keep a min-heap of the end times of the meetings currently in rooms.

For each meeting: if the earliest-ending meeting has already finished, reuse its room by popping it. Then push this meeting's end. The heap's size is the number of rooms in use, and its maximum is the answer.

python
import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])  # (9)
        heap = []                                  # (10) end times of busy rooms

        for start, end in intervals:  # (11)
            if heap and heap[0] <= start:  # (12)
                heapq.heappop(heap)                # that room is free again
            heapq.heappush(heap, end)  # (13)

        return len(heap)  # (14)

Line by line. (9) Sort the meetings by start. (10) A min-heap of the end times of the rooms in use, so the room that frees up soonest is at the front. (11) Take each meeting in start order. (12) If the room that frees up soonest is free by the time this meeting starts, reuse it by removing its old end time. (13) This meeting now occupies a room, so add its end time. (14) The heap's size is the number of rooms ever needed.

Only one pop per meeting is needed, even if several rooms have freed up. If two rooms are free you only need one for this meeting, and the other stays available for later — the heap's size is still correct.

The final heap size is the answer, because the heap only ever shrinks when a room is genuinely reused, so its peak equals its final size.

O(n \log n) time, O(n) space.

Which to write ​

The heap version reads more like the story — rooms with meetings in them — and it extends when you need to know which room each meeting used, since you can store room identifiers alongside the end times.

The sweep line is slightly faster and generalises further, and it is the one to reach for when the question is about counts rather than assignments.

Say both, pick one, and say why.

The sweep line, generalised ​

This is the main idea to take away from the whole chapter.

Convert each interval into two events, sort all events by time, and sweep with a running count.

python
events = []
for start, end in intervals:
    events.append((start, +1))
    events.append((end, -1))
events.sort()          # ties: -1 before +1, so an ending frees a room first

The tie-break matters. At equal times you want the -1 processed first, so a meeting ending at 10 frees a room for one starting at 10. Sorting tuples does this automatically because -1 < +1.

It solves a large family:

  • Maximum concurrent anything — meetings, downloads, database connections, aircraft in a sector.
  • Car Pooling (LeetCode 1094) — passengers boarding and leaving, with a capacity check.
  • My Calendar II and III — counting double and triple bookings.
  • The skyline problem (LeetCode 218) — a sweep line with a heap of building heights.
  • Rate limiting and capacity planning in production systems, which is Chapter 11.3.

Edge cases ​

  • No overlaps. One room.
  • Every meeting overlaps every other. As many rooms as meetings.
  • A meeting ends exactly when another starts. The room is reused.

Complexity ​

O(n \log n) time and O(n) space for both solutions.

  • Time Complexity: O(n \log n). Sorting the arrays (or using a heap) takes O(n \log n) time. The subsequent sweeping (or heap push/pops) takes O(n) time.
  • Space Complexity: O(n) extra space to store the separated start and end arrays (or the heap).

If the times were small whole numbers in a known range, you could use a difference array instead. Add 1 at each start and subtract 1 at each end, then take a running sum and find its maximum. That is O(n + T), where T is the time range. It is the bounded-values trick from 4.4.5. Name it as the improvement when times are, say, minutes in a day.

What the interviewer will push on ​

"Why can you separate starts from ends?" You are counting concurrency, and the pairing does not affect the count.

"What happens at equal times?" An end must be processed before a start, or a reusable room is missed.

"Why is the heap's size the answer?" It holds exactly the meetings currently occupying rooms.

"Why only one pop per meeting?" You only need one room for one meeting.

"What if you needed to know which room each meeting used?" Store room ids in the heap alongside the end times.

"What if the times were minutes in a day?" A difference array, O(n + 1440).

One thing to volunteer: name the sweep line and give one non-meeting use of it. It is the most transferable technique in the interval chapter, and interviewers notice when a candidate has a name for what they are doing.

Next: 4.27.6 Minimum Interval to Include Each Query — the hardest interval problem, combining sorting, a heap and offline query processing.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet