Neetcode 150 - Meeting Room 2

1. 🧩 Input Example

intervals = [ Interval(0, 30), Interval(5, 10), Interval(15, 20) ]

2. 🧠 Min-Heap Solution

intervals.sort(key=lambda x: x.start)
min_heap = []

for interval in intervals:
    if min_heap and min_heap[0] <= interval.start:
        heapq.heappop(min_heap)
    heapq.heappush(min_heap, interval.end)

return len(min_heap)

2.1. ⚙️ Step-by-Step Dry Run

Step	Interval	Heap Before	Action	Heap After	Rooms Used
1	(0, 30)	[]	push 30	[30]	1
2	(5, 10)	[30]	5 < 30 → overlap → push 10	[10, 30]	2
3	(15, 20)	[10, 30]	10 ≤ 15 → pop 10, push 20	[20, 30]	2

Result: len(heap) = 2

✅ Output → 2

💡 Explanation

  • The heap keeps end times of ongoing meetings.

  • If the earliest end time (heap[0]) ≤ next meeting’s start → reuse that room.

  • Otherwise, allocate a new one.

  • The heap’s maximum size = number of rooms needed.

🕒 Time & Space

  • Time: O(N log N) → sort + heap ops

  • Space: O(N) → heap can grow up to N

3. Sweep Line (Prefix Sum / Delta Map)

mp = defaultdict(int)
for i in intervals:
    mp[i.start] += 1
    mp[i.end] -= 1

prev = 0
res = 0
for i in sorted(mp.keys()):
    prev += mp[i]
    res = max(res, prev)
return res

⚙️ Step-by-Step Dry Run

Time	Change	Current Count	Max Rooms
0	+1	1	1
5	+1	2	2
10	-1	1	2
15	+1	2	2
20	-1	1	2
30	-1	0	2

✅ Output → 2

💡 Explanation

  • We record every meeting start as +1 (need a room)

  • Every meeting end as -1 (free a room)

  • Sorting times and accumulating these deltas shows how many rooms are needed at each point.

  • The max accumulated value = max rooms required.

🕒 Time & Space

  • Time: O(N log N) (sorting keys)

  • Space: O(N) (hashmap)

4. Two Pointers (Separate Starts & Ends)

start = sorted([i.start for i in intervals])
end = sorted([i.end for i in intervals])

res = count = 0
s = e = 0
while s < len(intervals):
    if start[s] < end[e]:
        count += 1
        s += 1
    else:
        e += 1
        count -= 1
    res = max(res, count)
return res

⚙️ Dry Run

Step	start[s]	end[e]	Action	count	res
1	0	10	0<10 → new meeting	1	1
2	5	10	5<10 → overlap	2	2
3	15	10	15≥10 → end one meeting	count=1, e=1	2
4	15	20	15<20 → start new	count=2, s=3	2

✅ Output → 2

💡 Explanation

  • Sort start and end times separately.

  • Use two pointers to walk through:

  • When a new meeting starts before the previous one ends → need a new room.

  • When a meeting ends → free a room.

  • Track max(count).

🕒 Time & Space

  • Time: O(N log N)

  • Space: O(N)

5. Greedy (Timeline Events)

time = []
for i in intervals:
    time.append((i.start, 1))
    time.append((i.end, -1))
time.sort(key=lambda x: (x[0], x[1]))

res = count = 0
for t in time:
    count += t[1]
    res = max(res, count)
return res

⚙️ Dry Run

After expanding and sorting:

[(0, +1), (5, +1), (10, -1), (15, +1), (20, -1), (30, -1)]

Time	Change	count	res
0	+1	1	1
5	+1	2	2
10	-1	1	2
15	+1	2	2
20	-1	1	2
30	-1	0	2

✅ Output → 2

💡 Explanation

  • Treat all events as (+1) for start and (-1) for end.

  • Sort chronologically (end before start if same time).

  • Keep a running sum count.

  • The max value of count during iteration = rooms needed.

🕒 Time & Space

  • Time: O(N log N)

  • Space: O(N)

6. Summary Comparison

1	Min-Heap	Keep end times of ongoing meetings	Heap	O(N log N)	O(N)	2
2	Sweep Line	Use delta counts for start/end	Map	O(N log N)	O(N)	2
3	Two Pointers	Separate sorted start/end	Arrays	O(N log N)	O(N)	2
4	Greedy	Merge all times and count active	List	O(N log N)	O(N)	2
Last Updated On October 21, 2025