Overview

Given \(N\) delivery workers and \(M\) delivery requests, this is a bipartite matching problem solved using a greedy approach, where we need to find the maximum number of requests that can be assigned under the constraint that each worker can only carry packages that do not exceed their maximum weight capacity.

Analysis

Key Insight

First, since we want to assign as many requests as possible, it is important to not waste the capacity of delivery workers.

For example, suppose there is a delivery worker with a maximum weight capacity of \(100\), and there are packages weighing \(10\) and \(90\). If we assign the \(10\)-weight package to this worker, there might be no other worker left who can carry the \(90\)-weight package.

From this observation, we can see that it is optimal to assign the weakest available worker to the lightest packages.

Problem with the Naive Approach

Trying all combinations of workers and requests would be \(O(N \times M)\), and when \(N, M\) are up to \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations in the worst case, resulting in TLE.

Solution: Sort + Two Pointers

Sort both the workers’ capacities \(S\) and the package weights \(D\) in ascending order, then match them greedily from the smallest. Specifically:

• Starting from the lightest package, assign the worker with the lowest capacity who can still carry it
• This preserves higher-capacity workers for heavier packages

Algorithm

1. Sort the workers’ maximum weights \(S\) in ascending order.
2. Sort the request package weights \(D\) in ascending order.
3. Initialize two pointers \(i\) (worker side) and \(j\) (request side) starting from \(0\).
4. Repeat the following:
   • If \(S[i] \geq D[j]\) (worker \(i\) can carry the package for request \(j\)), the match is successful. Increment \(count\) by \(1\) and advance both \(i\) and \(j\).
   • If \(S[i] < D[j]\) (worker \(i\) cannot carry the package for request \(j\)), then this worker cannot carry any remaining unassigned request either (since \(D\) is sorted in ascending order). Advance only \(i\) to try the next worker with higher capacity.
5. Stop when either pointer reaches the end. \(count\) is the answer.

Concrete Example

Workers: \(S = [3, 5, 8]\), Requests: \(D = [2, 6, 7]\) (already sorted)

Step	\(i\)	\(j\)	Comparison	Result
1	0	0	\(3 \geq 2\) ✔	Match, \(count=1\)
2	1	1	\(5 \geq 6\) ✘	Advance \(i\)
3	2	1	\(8 \geq 6\) ✔	Match, \(count=2\)
4	3	2	\(i = N\), terminate	Answer: 2

Complexity

• Time complexity: \(O(N \log N + M \log M)\) (dominated by sorting; the two-pointer scan is \(O(N + M)\))
• Space complexity: \(O(N + M)\) (storing the sorted arrays)

Implementation Notes

• By using sys.stdin.buffer.read() to read all input at once, input processing can be done efficiently even in Python.

• After sorting, the original indices are no longer needed, so there is no need to keep track of worker or request numbers.

• In the two-pointer approach, note that when a match fails, only the worker-side pointer is advanced. Think of it as skipping workers with insufficient capacity.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    S = sorted(int(input_data[2 + i]) for i in range(N))
    D = sorted(int(input_data[2 + N + j]) for j in range(M))
    
    count = 0
    i = 0
    j = 0
    while i < N and j < M:
        if S[i] >= D[j]:
            count += 1
            i += 1
            j += 1
        else:
            i += 1
    
    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.