Frontend School

Maximize Guest Capacity with Limited Cleaning Budget

DSA
medium

Maximize Guest Capacity with Limited Cleaning Budget

Medium
Greedy
Sorting
Optimization

Overview

At OYO, optimizing resource allocation is crucial for maximizing operational efficiency and revenue, especially during peak seasons. As a hotel chain, we manage various room types, each with different capacities and associated cleaning costs. To prepare for high demand, we need a strategic plan to maximize the number of guests we can accommodate given a finite cleaning budget.

This problem challenges you to develop an algorithm that selects room configurations to maximize total guest capacity while adhering to a strict cleaning budget. This directly impacts our ability to serve more customers and generate higher overall revenue.

What you need to do / Task

Your task is to implement a function maximizeGuestCapacity that, given a list of available room types and a total cleaning budget, calculates the maximum total guest capacity that can be achieved.

For each room type, you are provided with:

  1. The number of availableRooms of that type.
  2. The guestsPerRoom (how many guests a single room of this type can accommodate).
  3. The cleaningCostPerRoom (the cost to clean one room of this type).

Your function should decide how many rooms of each type to utilize, ensuring the total cleaning cost does not exceed the totalCleaningBudget, and the total guest capacity is maximized.

Input & output

Function Signature:

function maximizeGuestCapacity(roomTypes: number[][], totalCleaningBudget: number): number;

Input:

  • roomTypes: A number[][] where each inner array [availableRooms, guestsPerRoom, cleaningCostPerRoom] represents a specific room type.
    • availableRooms: An integer representing the total number of rooms of this type available.
    • guestsPerRoom: An integer representing the maximum number of guests a single room of this type can accommodate.
    • cleaningCostPerRoom: An integer representing the cost to clean one room of this type.
  • totalCleaningBudget: An integer representing the maximum total budget available for cleaning all chosen rooms.

Output:

  • A number representing the maximum total guest capacity that can be achieved within the totalCleaningBudget.

Clarifications

  • If cleaningCostPerRoom is 0, it means the room type requires no budget for cleaning. These rooms should be prioritized as they offer guest capacity for free.
  • You can use any number of rooms of a given type, up to its availableRooms limit.
  • All input values (availableRooms, guestsPerRoom, cleaningCostPerRoom, totalCleaningBudget) will be non-negative integers.
  • guestsPerRoom will always be positive (> 0).
  • The goal is to maximize the sum of guestsPerRoom for all chosen rooms.

Examples

1

Example 1

Input:

roomTypes = [[1, 10, 5], [2, 5, 2]], totalCleaningBudget = 10

Output:

20

Note:

Room Type 1: 1 room, 10 guests, 5 cost. Ratio: 10/5 = 2.0 guests/cost. Room Type 2: 2 rooms, 5 guests, 2 cost. Ratio: 5/2 = 2.5 guests/cost.

Sorted by ratio (descending):

  1. Room Type 2: [2, 5, 2] (Ratio 2.5)
  2. Room Type 1: [1, 10, 5] (Ratio 2.0)

Allocation:

  • Take all 2 rooms of Type 2: Guests = 2 * 5 = 10. Cost = 2 * 2 = 4. Budget remaining = 10 - 4 = 6.
  • Take all 1 room of Type 1: Guests = 1 * 10 = 10. Cost = 1 * 5 = 5. Budget remaining = 6 - 5 = 1. Total guests = 10 + 10 = 20.
2

Example 2

Input:

roomTypes = [[3, 2, 10], [1, 10, 100]], totalCleaningBudget = 50

Output:

6

Note:

Room Type 1: 3 rooms, 2 guests, 10 cost. Ratio: 2/10 = 0.2 guests/cost. Room Type 2: 1 room, 10 guests, 100 cost. Ratio: 10/100 = 0.1 guests/cost.

Sorted by ratio (descending):

  1. Room Type 1: [3, 2, 10] (Ratio 0.2)
  2. Room Type 2: [1, 10, 100] (Ratio 0.1)

Allocation:

  • Take Room Type 1: Budget 50. Each room costs 10. We can afford 50/10 = 5 rooms. We only have 3 available rooms of this type. So, take all 3 rooms. Guests = 3 * 2 = 6. Cost = 3 * 10 = 30. Budget remaining = 50 - 30 = 20.
  • Take Room Type 2: Budget 20. Each room costs 100. Cannot afford any rooms of this type. Total guests = 6.
3

Example 3

Input:

roomTypes = [[1, 100, 0], [5, 1, 10]], totalCleaningBudget = 20

Output:

102

Note:

Room Type 1: 1 room, 100 guests, 0 cost. Ratio: 100/0 = Infinity (prioritized). Room Type 2: 5 rooms, 1 guest, 10 cost. Ratio: 1/10 = 0.1 guests/cost.

Sorted by ratio (descending):

  1. Room Type 1: [1, 100, 0] (Ratio Infinity)
  2. Room Type 2: [5, 1, 10] (Ratio 0.1)

Allocation:

  • Take all 1 room of Type 1: Guests = 1 * 100 = 100. Cost = 1 * 0 = 0. Budget remaining = 20 - 0 = 20.
  • Take Room Type 2: Budget 20. Each room costs 10. We can afford 20/10 = 2 rooms. We have 5 available. So, take 2 rooms. Guests = 2 * 1 = 2. Cost = 2 * 10 = 20. Budget remaining = 20 - 20 = 0. Total guests = 100 + 2 = 102.

Constraints

Constraints & assumptions

  • 1 <= roomTypes.length <= 10^5
  • 0 <= availableRooms <= 10^9
  • 1 <= guestsPerRoom <= 10^9
  • 0 <= cleaningCostPerRoom <= 10^9
  • 0 <= totalCleaningBudget <= 10^18 (Note: totalCleaningBudget can be large, use 64-bit integer if language requires)
  • The total guest capacity and total cleaning cost can exceed standard 32-bit integer limits, so use 64-bit integers (e.g., number in JavaScript/TypeScript, long in Java/C#) for calculations involving sums.

Out of scope

  • Error handling for invalid input formats (e.g., negative guestsPerRoom). Assume inputs adhere to the specified constraints.
  • Optimizing for factors other than guest capacity (e.g., specific room type distribution, customer satisfaction scores).

What interviewers evaluate

  • Correctness of Greedy Strategy: Demonstrates a clear understanding and correct application of a greedy approach to solve the optimization problem.
  • Efficiency: Achieves optimal time complexity, typically O(N log N) due to sorting, where N is the number of room types.
  • Edge Case Handling: Properly handles scenarios such as zero cleaning cost rooms, zero budget, or insufficient budget for any room.
  • Data Type Handling: Correctly uses appropriate data types for potentially large sums (e.g., totalCleaningBudget, maxGuests).
  • Code Quality: Writes clean, readable, and well-structured code with appropriate comments where necessary.

Loading editor...