Frontend School

Optimal Room Allocation

DSA
medium

Optimal Room Allocation

Medium
Binary Search
Arrays

Overview

At Oyo, efficiently managing housekeeper assignments for room preparation is crucial for operational excellence and guest satisfaction. We need a system to distribute the workload fairly among available housekeepers, especially when dealing with multiple hotels, each with varying numbers of rooms.

This problem challenges you to find the most balanced way to allocate rooms from a series of hotels to a fixed number of housekeepers. The goal is to minimize the maximum number of rooms any single housekeeper is responsible for, ensuring an equitable distribution of work.

What you need to do / Task

Implement a function allocateRooms that determines the minimum possible value for the maximum number of rooms any single housekeeper needs to prepare. You are given an array representing the number of rooms in a sequence of hotels and the total number of housekeepers available.

Deliverables:

  1. Implement the allocateRooms function.
  2. Ensure your solution is efficient, meeting the specified time and space complexity requirements.

Input & output

  • roomCounts: number[]
    • An array where roomCounts[i] represents the number of rooms in the i-th hotel.
  • k: number
    • The total number of housekeepers available for allocation.
  • Returns: number
    • The minimum possible value of the maximum rooms assigned to any single housekeeper.

Clarifications

  • Contiguous Blocks: A housekeeper can only be assigned rooms from a contiguous block of hotels. For example, if roomCounts = [10, 20, 30, 40] and k=2, one housekeeper could take [10, 20] (sum 30) and the other [30, 40] (sum 70). They cannot take [10, 40] and [20, 30] as these are not contiguous blocks.
  • Housekeeper Count: The number of housekeepers k will always be less than or equal to the total number of hotels (roomCounts.length).
  • Positive Room Counts: All roomCounts[i] values will be positive integers.

Examples

1

Example 1

Input:

roomCounts = [7, 2, 5, 10, 8], k = 2

Output:

18

Note:

The hotels can be split into two groups: [7, 2, 5] (sum = 14) and [10, 8] (sum = 18). The maximum rooms assigned to any housekeeper is 18. No other valid contiguous split can achieve a smaller maximum.

2

Example 2

Input:

roomCounts = [1, 2, 3, 4, 5], k = 3

Output:

7

Note:

One optimal contiguous split is [1, 2] (sum=3), [3, 4] (sum=7), [5] (sum=5). The maximum rooms assigned to any housekeeper in this split is 7.

3

Example 3

Input:

roomCounts = [10, 20, 30], k = 1

Output:

60

Note:

With only one housekeeper, they must prepare all rooms from all hotels, summing up to 60.

Constraints

Constraints & assumptions

  • 1 <= roomCounts.length <= 10^5
  • 1 <= roomCounts[i] <= 10^4
  • 1 <= k <= roomCounts.length
  • Time complexity: Your solution should aim for O(N log S), where N is the number of hotels (roomCounts.length) and S is the sum of all rooms.
  • Space complexity: Your solution should aim for O(1) auxiliary space (excluding input/output storage).

Out of scope

  • Handling invalid input types (e.g., non-numeric values, negative room counts).
  • Optimizations beyond the target time and space complexity.

What interviewers evaluate

  • Correctness: The solution accurately identifies the minimum possible maximum rooms per housekeeper.
  • Algorithm Efficiency: The chosen algorithm efficiently leverages binary search on the answer space.
  • Edge Case Handling: The solution correctly addresses scenarios like k=1 (one housekeeper) or k=roomCounts.length (each housekeeper gets one hotel).
  • Code Quality: The code is clean, readable, well-structured, and easy to understand.

Loading editor...