Abstract / Summary

Given a list of meeting time intervals, determine if it is possible for a given number of rooms to host all meetings without overlap.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 51% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Heap (Priority Queue)
• Simulation
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation solves the problem of assigning a set of meetings to a fixed number of rooms while tracking which room hosts the most meetings. It processes meetings in chronological order, maintains two priority queues-one for free rooms and one for ongoing meetings-and updates a counter per room. The final result is the index of the room with the highest meeting count, with ties resolved by the smallest index.

Key Steps

The algorithm begins by initializing three data structures.

rooms    = list(range(n))          # min-heap of available rooms
ongoing  = []                      # min-heap of active meetings (end, room)
occupied = [0] * n                 # meeting count per room

The list of meetings is sorted by start time, guaranteeing that earlier meetings are considered first.

for s, e in sorted(meetings):

For each meeting, the code first releases any rooms whose meetings have already finished by the current start time. This is done by repeatedly popping from the ongoing heap while the earliest ending meeting ends no later than the current start. Each released room is pushed back onto the rooms heap, making it available for future assignments.

while ongoing and ongoing[0][0] <= s:
    when, where = heappop(ongoing)
    heappush(rooms, where)

After freeing rooms, the algorithm decides whether the upcoming meeting can start on time or must be delayed. If the rooms heap is non-empty, the smallest-indexed free room is selected, and the meeting proceeds at its scheduled time.

if rooms:
    where = heappop(rooms)        # start on time

If no rooms are free, the meeting must wait for the earliest finishing ongoing meeting. The code extracts that meeting, computes the delay, and extends the current meeting’s end time accordingly.

else:
    delayed, where = heappop(ongoing)
    e += delayed - s               # delayed meeting

Regardless of whether the meeting was delayed, it is added to the ongoing heap with its (potentially adjusted) end time and the assigned room. The room’s meeting counter is incremented.

heappush(ongoing, (e, where))
occupied[where] += 1

When all meetings have been processed, the algorithm determines the maximum count in occupied and returns the first room index that achieves this maximum.

most = max(occupied)
for i, o in enumerate(occupied):
    if o == most:
        return i

Edge Cases Handled

The code gracefully handles meetings that start at the exact moment another meeting ends. The condition ongoing[0][0] <= s ensures that a room becomes available for a meeting that begins at the same timestamp as the previous meeting’s end.

When multiple meetings share the same start time, the sorted order preserves deterministic processing, and the priority queues guarantee that the smallest-indexed free room is always chosen first.

If all rooms are occupied when a meeting is scheduled, the algorithm correctly computes the delay by subtracting the original start time from the earliest finishing meeting’s end time, then adds that difference to the meeting’s original end time. This adjustment preserves the meeting’s original duration while shifting its start forward.

The final selection of the most-booked room resolves ties by returning the smallest index, because the loop iterates in increasing order and returns on the first match.

Performance Optimizations

The use of two min-heaps provides efficient retrieval of the next available room and the earliest finishing meeting. Inserting and removing elements from a heap operates in logarithmic time relative to the number of rooms, which keeps the overall processing time low even when the number of meetings is large.

By reusing the same rooms heap for both initial room indices and rooms that become free later, the implementation avoids the overhead of rebuilding or scanning a list of free rooms.

The algorithm updates the meeting count in a simple list indexed by room number, allowing constant-time increments without additional data structures.

Sorting the meetings once at the beginning ensures that the main loop processes them in chronological order without needing to perform any additional ordering work during iteration.

Overall, the combination of sorted input, heap-based resource management, and direct array indexing yields a solution that scales well with both the number of rooms and the number of meetings.

Imagine a hotel with several rooms where people want to hold meetings. Each room has a number to help identify it. The process starts by looking at a list of requested meetings and putting them in order by their start times.

First, the code checks if any current meetings have ended by the time a new one is supposed to begin. If a room has become empty, it is added back to a pile of available rooms so it can be used again.

Next, the code looks for a place to put the new meeting. If there is a room ready and waiting, it is taken immediately. If all rooms are full, the code finds the room that will be free the soonest and waits for that one to become available, which means the new meeting will start a little bit later than planned.

Every time a meeting starts, the room is marked as busy until the new end time, and a little counter for that specific room goes up by one. This keeps track of how many meetings happen in each room.

Once every meeting has been scheduled, the code looks at all the counters to see which rooms hosted the most sessions. If a few rooms happen to have the same highest number, it selects the one with the smallest number.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python	TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java		Go	Python	TS
	Progiez	C++		Java			Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	martianoff				Scala
	varunu28			Java
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
martianoff	Scala
varunu28	Java
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality