Nutanix

Problem Statement Data Engineers must schedule n long-running tasks on remote servers while minimizing total cost. There are two available servers: 1. Paid Server: Processing task i costs cost[i] and takes time[i] units of time. 2. Free Server: Processing any task costs 0 and takes 1 unit of time. However, the free server can only process tasks while the paid server is occupied. Since the free server processes tasks at a rate of 1 per time unit, running task i on the paid server allows time[i] other tasks to be processed on the free server simultaneously. Example Input: n = 4, cost = [1, 1, 3, 4], time = [3, 1, 2, 3] * Strategy: Schedule the first task (index 0) on the paid server. * Cost: 1. * Time on Paid: 3 units. * Effect: During these 3 units, the remaining 3 tasks are processed on the free server (taking 1 unit each). * Result: All 4 tasks are completed for a total cost of 1. Function Description * cost[n]: Integer array representing the cost of each task on the paid server. * time[n]: Integer array representing the duration of each task on the paid server. Constraints * $1 \le n \le 10^3$ * $1 \le cost[i] \le 10^6$ * $1 \le time[i] \le 10^3$ Solution Approach This problem can be modeled as a variation of the 0/1 Knapsack Problem. The objective is to select a subset of tasks to run on the paid server such that the remaining tasks can be covered by the free server. * If task i is chosen for the paid server, it contributes time[i] units of "free server capacity." * Additionally, task i itself is completed, effectively covering 1 task count. * Therefore, running task i on the paid server contributes a total "value" of time[i] + 1 towards the total number of tasks n. The problem reduces to finding the minimum cost to achieve a total combined time value of at least n. Algorithm: 1. Initialize a DP array dp of size n + 1 with infinity, where dp[0] = 0. 2. dp[j] represents the minimum cost to cover j tasks. 3. Iterate through every task i with associated c = cost[i] and t = time[i]. 4. Update the DP table in reverse (from n down to 1): * dp[j] = min(dp[j], dp[max(0, j - t - 1)] + c) 5. The answer is stored in dp[n]. Time Complexity: $O(n^2)$ Space Complexity: $O(n)$