Maximize Guest Capacity with Limited Cleaning Budget
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.
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:
availableRooms of that type.guestsPerRoom (how many guests a single room of this type can accommodate).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.
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:
number representing the maximum total guest capacity that can be achieved within the totalCleaningBudget.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.availableRooms limit.availableRooms, guestsPerRoom, cleaningCostPerRoom, totalCleaningBudget) will be non-negative integers.guestsPerRoom will always be positive (> 0).guestsPerRoom for all chosen rooms.Examples
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):
Allocation:
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):
Allocation:
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):
Allocation:
Constraints
1 <= roomTypes.length <= 10^50 <= availableRooms <= 10^91 <= guestsPerRoom <= 10^90 <= cleaningCostPerRoom <= 10^90 <= totalCleaningBudget <= 10^18 (Note: totalCleaningBudget can be large, use 64-bit integer if language requires)number in JavaScript/TypeScript, long in Java/C#) for calculations involving sums.guestsPerRoom). Assume inputs adhere to the specified constraints.O(N log N) due to sorting, where N is the number of room types.totalCleaningBudget, maxGuests).Loading editor...