easyGreedyPattern: Greedy
Maximize Satisfied Resource Requests Solution
Problem Statement
You are given a total `resourceCapacity` (a non-negative integer) and an array `requestAmounts`, where each element `requestAmounts[i]` represents the amount of resource required for a specific request. Your task is to determine the maximum number of requests that can be fully satisfied given the `resourceCapacity`. A request is fully satisfied if its `requestAmount` is less than or equal to the remaining `resourceCapacity`, and the `resourceCapacity` is then reduced by that amount.
Examples
Example 1:
Input:resourceCapacity = 10, requestAmounts = [2, 5, 3, 1]
Output:3
Explanation: First, sort the `requestAmounts` to get `[1, 2, 3, 5]`.
1. Satisfy request for `1`. Remaining capacity: `10 - 1 = 9`. Satisfied count: `1`.
2. Satisfy request for `2`. Remaining capacity: `9 - 2 = 7`. Satisfied count: `2`.
3. Satisfy request for `3`. Remaining capacity: `7 - 3 = 4`. Satisfied count: `3`.
4. Cannot satisfy request for `5` as `5 > 4`.
Therefore, a maximum of 3 requests can be fully satisfied.
Example 2:
Input:resourceCapacity = 7, requestAmounts = [10, 8]
Output:0
Explanation: First, sort the `requestAmounts` to get `[8, 10]`.
1. Cannot satisfy request for `8` as `8 > 7`.
No requests can be fully satisfied.
Constraints
- 0 <= resourceCapacity <= 10^9
- 0 <= requestAmounts.length <= 10^5
- 1 <= requestAmounts[i] <= 10^9
Time: O(N log N) Space: O(N)
The optimal approach is to use a greedy strategy: sort the `requestAmounts` in ascending order. Then, iterate through the sorted requests, subtracting each request's amount from the `resourceCapacity` as long as there is enough capacity remaining. Count the number of requests successfully satisfied. This ensures we always prioritize smaller requests, maximizing the number of requests that can fit within the budget.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def main():
resource_capacity = int(sys.stdin.readline())
request_amounts_line = sys.stdin.readline().strip()
request_amounts = []
if request_amounts_line:
request_amounts = list(map(int, request_amounts_line.split()))
# Sort the requests in ascending order to satisfy the cheapest requests first
request_amounts.sort()
satisfied_requests = 0
for amount in request_amounts:
if resource_capacity >= amount:
resource_capacity -= amount
satisfied_requests += 1
else:
# Cannot satisfy this request, nor any larger ones, so break
break
print(satisfied_requests)
if __name__ == "__main__":
main()