Ward Support Passes
Maximum matches between requirement and capacity arrays with limited boosts
A hospital ward is planning a support shift. Each support request needs one orderly, and each orderly can handle at most one request during the shift.
The array tasks contains the readiness requirement of each request. The array readiness contains the readiness score of each available orderly. An orderly can handle a request when their readiness score is at least that request's requirement.
The supervisor has passes temporary training passes. A pass increases one orderly's readiness by exactly boost for this shift. Each orderly may receive at most one pass, and using passes is optional.
You may choose any subset of requests and any subset of orderlies, and pair them in any order. Return the maximum number of requests that can be handled, using at most passes training passes.
Equal values still represent separate requests or separate orderlies. The arrays are not necessarily sorted.
Examples
Example 1
Input: tasks = [4,6,9], readiness = [2,4,9], passes = 1, boost = 4 Output: 3
All three requests can be handled. Give a pass to the orderly with readiness 2 so they can handle requirement 6; the other two orderlies handle requirements 4 and 9.
Example 2
Input: tasks = [5,8], readiness = [3,3], passes = 1, boost = 3 Output: 1
At most one request can be handled. Neither orderly can handle requirement 8 even with a pass, but a boosted orderly can handle requirement 5.
Example 3
Input: tasks = [3,3,7], readiness = [2,3,5], passes = 0, boost = 100 Output: 2
No passes are available. Two separate requests with requirement 3 can be paired with the two orderlies whose readiness scores are at least 3.
Constraints
- 0 <= len(tasks), len(readiness) <= 5000
- 0 <= tasks[i], readiness[i] <= 10^9
- 0 <= passes <= len(readiness)
- 0 <= boost <= 10^9
Let n and m be the two array lengths and K = min(n, m). Sorting followed by binary search takes O(n log n + m log m + K log(K + 1)) time and O(n + m) auxiliary space. An empty request list or an empty orderly list yields zero.
Hints
Show hint 1Hint 1
For a proposed total k, it is sufficient to consider the k easiest requests and the k strongest orderlies. Feasibility is monotone in k.
Show hint 2Hint 2
Process those orderlies from weakest to strongest. Keep eligible requests in a deque. If the easiest eligible request needs no pass, take it; otherwise spend a pass on the hardest eligible request.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return a valid assignment using original request and orderly indices?
- What changes if each orderly has a different boost amount rather than a shared boost?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem