Meeting Rooms

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

Calendar systems need to allocate conference rooms: given a set of meetings, what is the minimum number of rooms so every meeting runs without overlap? You will solve that, then assign specific room IDs, then handle a capped room count with priority eviction.

Each meeting is a half-open interval [start, end). A meeting ending at t and one starting at t may share a room.

Level 1 - Minimum rooms

Find the minimum number of rooms so every meeting runs without overlap.

Example:

intervals = [(0, 30), (5, 10), (15, 20)]
min_meeting_rooms(intervals)  -> 2
 
# (0,30) occupies room A the whole time.
# (5,10) overlaps with (0,30), so it needs room B.
# (15,20) starts after (5,10) ends; reuses room B.

Level 2 - Room assignment

def assign_rooms(intervals: list[tuple[int, int]]) -> list[int]: ...

Return a list where result[i] is the room ID assigned to intervals[i]. Reuse the smallest available room ID. Room IDs start at 0. The output is indexed by the original input order, not sort order.

Example:

intervals = [(0, 30), (5, 10), (15, 20)]
assign_rooms(intervals)  -> [0, 1, 1]
 
# room 0: (0,30)   room 1: (5,10) then (15,20) reuses room 1
# Result indexed by original input order, not sort order.

Level 3 - Capacity with priority eviction

Add a fixed max_rooms cap and a per-meeting priority:

def schedule_with_priority(
    intervals: list[tuple[int, int, int]],  # (start, end, priority)
    max_rooms: int,
) -> list[int]:
    """Return the indices of accepted meetings."""

When a meeting arrives and all rooms are busy: if any in-room meeting has strictly lower priority, evict it and take its room. Otherwise drop this meeting.

Resolution rules:

Free meetings whose end <= current meeting's start before checking capacity.
Equal priorities: incumbent wins (no eviction).
A meeting that gets evicted is removed from the accepted list.

Example:

intervals = [(0, 100, 1), (10, 20, 5)]   # (start, end, priority)
schedule_with_priority(intervals, max_rooms=1)  -> [1]
 
# (0,100) priority 1 gets the room first.
# (10,20) priority 5 evicts it; index 0 is removed from accepted list.
# Result: only index 1 accepted.

Patterns used

Foundations primers this challenge draws on.

Greedy

Heaps

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed