Overview

There are delivery workers and delivery requests, each given a carrying capacity and a package weight, respectively. Each delivery worker can accept at most one request, and each request can be assigned to at most one delivery worker. The problem asks for the maximum number of requests that can be processed.

Analysis

The goal of this problem is to “maximize the number of assignable pairs.” A naive approach would be to try all combinations of delivery workers and requests, but this takes \(O(NM)\) and is impractical given the large constraints (TLE).

The key observation is that “it is better to assign delivery workers with lower capacity to lighter packages.” This is because delivery workers with higher capacity can also handle heavier packages, so they should be saved for later. In other words, a greedy approach seems applicable.

Specifically, we think as follows: - Sort the delivery workers’ capacities \(S\) and the requests’ weights \(D\) in ascending order. - Go through the requests from lightest to heaviest, and for each one, select the delivery worker with the lowest capacity who can handle it. - Since a delivery worker cannot be reused once assigned, we only need to search from the next available delivery worker onward.

This allows us to efficiently find the maximum number of assignments.

Algorithm

1. Sort the delivery workers’ capacity list \(S\) and the requests’ weight list \(D\) in ascending order.
2. Initialize the delivery worker index s_idx to 0.
3. For each request \(d\), do the following:
   • Search for the delivery worker with the smallest capacity that is at least \(d\), starting from index s_idx onward in \(S\) (using binary search bisect_left).
   • If found, assign that delivery worker and advance s_idx by 1.
4. Output the number of assignments made.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  (Dominated by sorting; the subsequent processing is linear)
• Space complexity: \(O(1)\)
  (Constant space excluding the input arrays)

Implementation Notes

• Use bisect.bisect_left to efficiently find the smallest delivery worker that satisfies the condition.

• By specifying lo=s_idx, we can skip delivery workers that have already been used.

• Be careful not to forget sorting.

  Source Code

import bisect

N, M = map(int, input().split())
S = list(map(int, input().split()))
D = list(map(int, input().split()))

S.sort()
D.sort()

count = 0
s_idx = 0

for d in D:
    # 配達員の中で、d 以上の能力を持つ最小の配達員を探す
    s_idx = bisect.bisect_left(S, d, lo=s_idx)
    if s_idx < N:
        count += 1
        s_idx += 1

print(count)

This editorial was generated by qwen3-coder-480b.