Maximum Number of Upgradable Servers

Medium

Snowflake

1 view

Topics:

Dynamic Programming

You are given n servers numbered from 0 to n - 1 and a 2D array servers where servers[i] = [type_i, end_i] means that the i^th server is of type_i and will be free to handle new requests starting from the time end_i. You are also given a 2D array queries where queries[i] = [arrival_i, upgradablei] means that a new request arrives at time arrival_i and requires all servers of type upgradable_i to be upgraded before the request can be handled.

When a server is upgraded, it will become free at the time arrival_i + 1. You can choose the order of the servers to upgrade; however, you cannot upgrade the same server twice.

You are required to find the maximum number of servers that can be upgraded for each query. Return an array of length queries.length such that answer[i] is the maximum number of servers that can be upgraded for the i^th query.

Note: The time in the system is discrete, meaning that the upgrade of the server happens before serving the request.

Example 1:

Input: servers = [[0,1],[1,2]], queries = [[1,0],[0,1]]
Output: [1,1]
Explanation:
For queries[0]: The request arrives at time 1 and requires all servers of type 0 to be upgraded.
Server 0 is of type 0 and is free to handle new requests starting from time 1.
Upgrading server 0 will make it free at time 2.
We can upgrade at most one server for queries[0].
For queries[1]: The request arrives at time 0 and requires all servers of type 1 to be upgraded.
Server 1 is of type 1 and is free to handle new requests starting from time 2.
We can upgrade server 1 to make it free at time 1.
We can upgrade at most one server for queries[1].

Example 2:

Input: servers = [[2,1],[2,2],[3,3]], queries = [[1,2],[2,3]]
Output: [2,1]
Explanation:
For queries[0]: The request arrives at time 1 and requires all servers of type 2 to be upgraded.
Server 0 is of type 2 and is free to handle new requests starting from time 1.
Server 1 is of type 2 and is free to handle new requests starting from time 2.
Upgrading server 0 will make it free at time 2.
Upgrading server 1 will make it free at time 2.
We can upgrade at most two servers for queries[0].
For queries[1]: The request arrives at time 2 and requires all servers of type 3 to be upgraded.
Server 2 is of type 3 and is free to handle new requests starting from time 3.
We can upgrade server 2 to make it free at time 3.
We can upgrade at most one server for queries[1].

Constraints:

n == servers.length
m == queries.length
1 <= n, m <= 2 * 10⁴
servers[i].length == 2
0 <= type_i <= 100
1 <= end_i <= 10⁵
queries[i].length == 2
0 <= arrival_i <= 10⁵
0 <= upgradable_i <= 100

Try coding it in LeetCode

Maximum Number of Upgradable Servers

Medium

Snowflake

1 view

Topics:

Dynamic Programming

You are given n servers numbered from 0 to n - 1 and a 2D array servers where servers[i] = [type_i, end_i] means that the i^th server is of type_i and will be free to handle new requests starting from the time end_i. You are also given a 2D array queries where queries[i] = [arrival_i, upgradablei] means that a new request arrives at time arrival_i and requires all servers of type upgradable_i to be upgraded before the request can be handled.

When a server is upgraded, it will become free at the time arrival_i + 1. You can choose the order of the servers to upgrade; however, you cannot upgrade the same server twice.

You are required to find the maximum number of servers that can be upgraded for each query. Return an array of length queries.length such that answer[i] is the maximum number of servers that can be upgraded for the i^th query.

Note: The time in the system is discrete, meaning that the upgrade of the server happens before serving the request.

Example 1:

Input: servers = [[0,1],[1,2]], queries = [[1,0],[0,1]]
Output: [1,1]
Explanation:
For queries[0]: The request arrives at time 1 and requires all servers of type 0 to be upgraded.
Server 0 is of type 0 and is free to handle new requests starting from time 1.
Upgrading server 0 will make it free at time 2.
We can upgrade at most one server for queries[0].
For queries[1]: The request arrives at time 0 and requires all servers of type 1 to be upgraded.
Server 1 is of type 1 and is free to handle new requests starting from time 2.
We can upgrade server 1 to make it free at time 1.
We can upgrade at most one server for queries[1].

Example 2:

Input: servers = [[2,1],[2,2],[3,3]], queries = [[1,2],[2,3]]
Output: [2,1]
Explanation:
For queries[0]: The request arrives at time 1 and requires all servers of type 2 to be upgraded.
Server 0 is of type 2 and is free to handle new requests starting from time 1.
Server 1 is of type 2 and is free to handle new requests starting from time 2.
Upgrading server 0 will make it free at time 2.
Upgrading server 1 will make it free at time 2.
We can upgrade at most two servers for queries[0].
For queries[1]: The request arrives at time 2 and requires all servers of type 3 to be upgraded.
Server 2 is of type 3 and is free to handle new requests starting from time 3.
We can upgrade server 2 to make it free at time 3.
We can upgrade at most one server for queries[1].

Constraints:

n == servers.length
m == queries.length
1 <= n, m <= 2 * 10⁴
servers[i].length == 2
0 <= type_i <= 100
1 <= end_i <= 10⁵
queries[i].length == 2
0 <= arrival_i <= 10⁵
0 <= upgradable_i <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for values in the `servers` and `upgrades` arrays, as well as the `budget`? Can they be negative or zero?
What should I return if the `servers` or `upgrades` arrays are empty or null?
Is the length of the `servers` array always the same as the length of the `upgrades` array? If not, what should I do?
Can a server be upgraded partially? Or does upgrading a server require the full cost (`upgrades[i]`)?
If multiple combinations of servers can be upgraded within the budget to achieve the same maximum number of upgraded servers, is any such combination acceptable?

Brute Force Solution

Approach

The brute force approach involves checking every possible combination of upgrades to see which one gives the most upgraded servers while staying within the budget. It's like trying every single possibility, no matter how inefficient, until we find the best one. We will consider all subsets of servers, simulating upgrading each subset and seeing if it's valid.

Here's how the algorithm would work step-by-step:

First, imagine you have a master list of all possible groups of servers you could upgrade. This includes upgrading no servers, upgrading just one server, upgrading two servers, and so on, all the way up to upgrading every single server.
Next, take the first group from your list. Pretend you've upgraded just those servers in that group.
Calculate the total cost of upgrading that specific group of servers.
If the total cost is more than your budget, then this combination is too expensive. Throw it out and move on to the next group.
If the total cost is within your budget, then count how many servers were upgraded in that group. We want to remember the maximum number of upgraded servers we can afford.
Continue going through each group on your master list, calculating the cost, and comparing it to your budget. If the group is affordable and has more upgraded servers than any group you've seen so far, remember this new group and how many servers were upgraded.
Once you've gone through every single possible group of servers, the group you remembered is the one that lets you upgrade the most servers while staying within your budget. That number is your final answer.

Code Implementation

def max_upgradable_servers(costs, budget):	num_servers = len(costs)
	max_upgraded_servers = 0

	# Iterate through all possible subsets of servers
	for i in range(2**num_servers):
		subset_cost = 0
		upgraded_servers_count = 0

		# Check each server to see if it's in the current subset
		for server_index in range(num_servers):
			# Check if the j-th bit is set in i, indicating server is upgraded
			if (i >> server_index) & 1:
				subset_cost += costs[server_index]
				upgraded_servers_count += 1

		#Determine if current server upgrade combination is feasible
		if subset_cost <= budget:
			#We want the max upgraded servers.
			max_upgraded_servers = max(max_upgraded_servers, upgraded_servers_count)

	return max_upgraded_servers

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm iterates through all possible subsets of servers to find the maximum number of upgradable servers within budget. For a set of n servers, there are 2^n possible subsets (each server can either be included or excluded in a subset). The algorithm checks the cost of each subset, leading to 2^n cost calculations and comparisons. Therefore, the time complexity is exponential with respect to the number of servers.

Space Complexity

O(1) – The brute force solution, as described, doesn't explicitly use auxiliary data structures that scale with the input size N (the number of servers). While generating combinations *could* involve storing them, the plain English explanation implies that each combination is generated, its cost evaluated, and then discarded. It only needs to keep track of the maximum number of upgraded servers found so far, and the cost of the current subset, both of which are constant space operations. Therefore, the auxiliary space used is constant, independent of N, resulting in O(1) space complexity.

Optimal Solution

Approach

We want to upgrade the maximum number of servers under certain constraints. The core idea is to sort the servers by their upgrade cost and then greedily upgrade the cheapest ones while respecting the resource limit.

Here's how the algorithm would work step-by-step:

First, organize the servers from least expensive to most expensive in terms of their upgrade cost.
Then, go through the servers in that order, starting with the cheapest.
For each server, check if upgrading it would exceed our available resources.
If we have enough resources, upgrade the server and reduce the available resources by the server's cost.
If we don't have enough resources, skip the server and move on to the next.
Keep doing this until we've checked all servers or we run out of resources.
The number of servers we successfully upgraded is the maximum number we can upgrade given the constraints.

Code Implementation

def maximum_upgradable_servers(server_costs, available_resources):
    number_of_servers = len(server_costs)
    server_indices = list(range(number_of_servers))

    # Sort servers based on their upgrade cost.
    server_indices.sort(key=lambda index: server_costs[index])

    upgraded_server_count = 0

    for server_index in server_indices:
        server_cost = server_costs[server_index]

        # Check if we can afford to upgrade the current server.
        if available_resources >= server_cost:
            available_resources -= server_cost
            upgraded_server_count += 1

    # The number of servers upgraded is the final result.
    return upgraded_server_count

Big(O) Analysis

Time Complexity

O(n log n) – The most significant operation in this solution is sorting the servers based on their upgrade costs. Sorting algorithms like merge sort or quicksort typically have a time complexity of O(n log n), where n is the number of servers. The subsequent loop iterates through the sorted list of servers once, performing a constant-time check for each server to determine if it can be upgraded. Therefore, the loop contributes O(n) to the overall time complexity. Since O(n log n) dominates O(n), the overall time complexity of the algorithm is O(n log n).

Space Complexity

O(N) – The algorithm sorts the servers based on upgrade cost. This sorting operation, depending on the implementation (e.g., using `sorted` in Python), typically creates a new sorted list of size N, where N is the number of servers. Therefore, the auxiliary space required is directly proportional to the number of servers. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
servers or upgrades array is null or empty	Return 0, as no upgrades are possible.
servers and upgrades have different lengths	Return 0, as an upgrade cost must exist for each server.
budget is zero	Return 0, as no upgrades are affordable.
upgrades array contains negative values	Treat the negative cost as a decrease in budget and potentially upgrade more servers.
upgrades array contains very large values (close to integer limit)	Be mindful of potential integer overflow when calculating cumulative costs, use long or equivalent if necessary.
All upgrade costs are greater than the budget	Return 0, as no server can be upgraded.
Sorting the upgrades array negatively impacts the original server indices if index tracking is needed in a variation of the problem	Maintain an index array alongside the upgrade costs if the original server association is crucial.
Large input size exceeding memory limitations for sorting or intermediate calculations.	Consider using in-place sorting algorithms (if allowed) or alternative approaches to minimize memory footprint.