A scheduler class that your favorite calendar uses to quickly find a meeting room (I was tasked to write it while interviewing at Uber)

meeting_scheduler.py

from sortedcontainers import SortedList
from collections import dict

class Interval:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end   
    
    def __repr__(self):
        return str(self)

    def __str__(self):
        return '(' + str(self.start) + ',' + str(self.end) + ')'
        
class Room:
    def __init__(self, name: str):
        self.name = name
        self.meetings = SortedList([], key = lambda x: x.start)
        
class Scheduler:
    def __init__(self, roomNames: List[str]):
        self.rooms = [Room(name) for name in roomNames]
        self.roomMap = dict((name, idx) for idx, name in enumerate(roomNames))
    
    def findRoom(self, meetingTime: Interval) -> str:
        '''
        Works in O(r*log(m)) time
        - Where r is the amount of rooms, and m is the max amount of meetings in the room
        '''
        for room in self.rooms:
            i = room.meetings.bisect_left(meetingTime)
            
            if i < len(room.meetings) and room.meetings[i].start < meetingTime.end:
                continue
            if i-1 >= 0 and room.meetings[i-1].end > meetingTime.start:
                continue
            
            room.meetings.add(meetingTime)
            return room.name
        
        raise Exception('no rooms available for meeting ' + str(meetingTime))
                
    def listIntervals(self, roomName: str) -> List[Interval]:
        '''
        Works in O(m) time
        - Where m is the amount of meetings in the room
        '''
        if roomName not in self.roomMap:
            raise Exception('no rooms available')
        
        roomIdx = self.roomMap[roomName]
        return [x for x in self.rooms[roomIdx].meetings]
    
def printSchedulerIntervals(scheduler: Scheduler, roomNames: List[str]) -> None:
    print('Rooms schedule:')
    for name in roomNames:
        print(name, scheduler.listIntervals(name))
    print()


roomNames = ['Airport', 'Carwash', 'Theater']
scheduler = Scheduler(roomNames)

scheduler.findRoom(Interval(3,4))
scheduler.findRoom(Interval(0,2))
scheduler.findRoom(Interval(2,3))
scheduler.findRoom(Interval(5,7))
scheduler.findRoom(Interval(10,15))
printSchedulerIntervals(scheduler, roomNames)

scheduler.findRoom(Interval(3,4))
scheduler.findRoom(Interval(5,6))
scheduler.findRoom(Interval(6,9))
scheduler.findRoom(Interval(0,1))
scheduler.findRoom(Interval(11,12))
printSchedulerIntervals(scheduler, roomNames)
    
scheduler.findRoom(Interval(0,16))
printSchedulerIntervals(scheduler, roomNames)
    
badIntervals = [
    Interval(0,16),
    Interval(0,5),
    Interval(11,17),
    Interval(5,6),
]
for badInterval in badIntervals:
    try:
        scheduler.findRoom(badInterval)
    except Exception as err:
        print('Caught an error:', err)

Output

Rooms schedule:
Airport [(0,2), (2,3), (3,4), (5,7), (10,15)]
Carwash []
Theater []

Rooms schedule:
Airport [(0,2), (2,3), (3,4), (5,7), (10,15)]
Carwash [(0,1), (3,4), (5,6), (6,9), (11,12)]
Theater []

Rooms schedule:
Airport [(0,2), (2,3), (3,4), (5,7), (10,15)]
Carwash [(0,1), (3,4), (5,6), (6,9), (11,12)]
Theater [(0,16)]

Caught an error: no rooms available for meeting (0,16)
Caught an error: no rooms available for meeting (0,5)
Caught an error: no rooms available for meeting (11,17)
Caught an error: no rooms available for meeting (5,6)