Data Center Drone Path Optimization
Apple's global data centers rely on efficient maintenance routines to ensure peak performance and reliability. Imagine a new generation of autonomous drones tasked with optimizing server maintenance. These drones traverse a grid of servers, collecting critical system data while adhering to strict power budgets. Your task is to develop an algorithm that helps a drone maximize the total 'criticality score' of collected data packets, given its limited processing budget and the various costs associated with each server.
This problem requires careful state management and optimization, reflecting the kind of complex resource allocation challenges faced in large-scale infrastructure management.
Implement the function maxCriticalityPath which calculates the maximum total criticality score a drone can collect by traversing a grid of servers from the top-left corner (0, 0) to the bottom-right corner (R-1, C-1). The drone can move in three directions:
(r, c) to (r+1, c)(r, c) to (r, c+1)(r, c) to (r+1, c+1)When the drone visits a server at (r, c), it collects its criticalityScore and incurs its processingCost. The drone has a maxBudget for processing power. It cannot visit a server if doing so would cause its total processing cost to exceed maxBudget.
Your solution should return the maximum possible total criticality score. If no valid path exists to the destination within the given budget, return -1.
Function Signature:
function maxCriticalityPath(criticalityScores: number[][], processingCosts: number[][], maxBudget: number): number
Input Parameters:
criticalityScores: A 2D array (matrix) of numbers, where criticalityScores[r][c] represents the criticality score obtained from visiting the server at row r and column c.processingCosts: A 2D array (matrix) of numbers, where processingCosts[r][c] represents the processing power consumed when visiting the server at row r and column c.maxBudget: A number representing the maximum total processing power the drone can expend.Output:
number representing the maximum total criticality score collected. Returns -1 if no valid path to (R-1, C-1) exists within maxBudget.Examples
Example 1
Input:
criticalityScores = [[10, 5], [1, 20]], processingCosts = [[1, 2], [3, 4]], maxBudget = 10
Output:
35
Note:
The optimal path is (0,0) -> (0,1) -> (1,1). Scores: 10 + 5 + 20 = 35. Costs: 1 + 2 + 4 = 7. Total cost 7 <= maxBudget 10.
Example 2
Input:
criticalityScores = [[10, 100], [1, 5]], processingCosts = [[1, 20], [3, 1]], maxBudget = 5
Output:
16
Note:
The optimal path is (0,0) -> (1,0) -> (1,1). Scores: 10 + 1 + 5 = 16. Costs: 1 + 3 + 1 = 5. Total cost 5 <= maxBudget 5. (0,0) -> (0,1) is not possible because (0,1) costs 20, exceeding the remaining budget (5-1=4).
Example 3
Input:
criticalityScores = [[10, 100], [1, 5]], processingCosts = [[100, 20], [3, 1]], maxBudget = 5
Output:
-1
Note:
The drone cannot even start at (0,0) as its processing cost (100) exceeds the maxBudget (5). No valid path exists.
Constraints
1 <= R, C <= 50 (where R is the number of rows and C is the number of columns).0 <= criticalityScores[r][c] <= 100 for all r, c.0 <= processingCosts[r][c] <= 100 for all r, c.0 <= maxBudget <= 5000.criticalityScores and processingCosts will always have R rows and C columns.O(R * C * maxBudget) time and space).Loading editor...