Dataford
Interview QuestionsInterview GuidesExperiencesMock InterviewsPricing
Get started

Algorithm with Complexity Analysis

EasyPython00:00
Practice interviewer
In session
5 left
00:00

Your question is Algorithm with Complexity Analysis. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Westgate Resorts wants to determine the minimum number of rooms required to honor a set of reservations without moving guests between rooms. Each reservation has a check-in time and a check-out time. Return the minimum number of rooms needed so that every reservation can be assigned a room.

A room becomes available at the exact check-out time, so a reservation beginning at that time can reuse the room.

Formal Specification

Implement min_rooms(reservations), where reservations is a list of two-element lists. Each reservation is represented as [check_in, check_out], with integer time values. Return an integer representing the maximum number of reservations that overlap at any instant.

Constraints

  • 0 <= reservations.length <= 10^5
  • Each reservation contains exactly two integers
  • 0 <= check_in < check_out <= 10^9
  • Check-out times are inclusive of room release, so check_in equal to check_out allows reuse
  • Return 0 when reservations is empty

Function Signature

def min_rooms(reservations):
Your solutionPython 3
You need to log in / sign up to run or submit.
Run your code to see test output