Overview

This is a problem where we need to match delivery workers with delivery requests according to given conditions and find the maximum number of assignments.

Analysis

This problem asks us to find a maximum matching that satisfies the given conditions. Each delivery worker can handle at most one request, and each request can be assigned to at most one delivery worker. The condition for delivery worker \(i\) to handle request \(j\) is \(S_i \geq D_j\).

A naive approach would be to try all possible combinations, but since \(N\) and \(M\) can be as large as \(2 \times 10^5\), a solution with \(O(N \times M)\) time complexity cannot finish within the time limit.

The key observation is that to assign as many requests as possible, it is better to assign each delivery worker the lightest possible package. In other words, by sorting the workers’ capacities \(S_i\) and the package weights \(D_j\) respectively, and then greedily matching them in order from smallest to largest, we can efficiently find the maximum number of matchings.

Algorithm

1. Sort the delivery workers’ maximum weights \(S\) and the request package weights \(D\) in ascending order.
2. Prepare two pointers \(i\) (for delivery workers) and \(j\) (for requests) for the sorted \(S\) and \(D\).
3. While both \(i\) and \(j\) are within the bounds of their respective arrays, repeat the following:
   • If the current delivery worker \(S[i]\) is greater than or equal to the current request \(D[j]\), the matching is successful: increment \(count\) and advance \(j\).
   • Always advance \(i\) to check the next delivery worker.
4. The final \(count\) is the maximum number of assignments.

The reason this greedy approach works correctly is that, in the sorted arrays, it is optimal to assign each package starting from the lightest to the smallest-capacity worker that can carry it. This allows us to reserve higher-capacity workers for heavier packages.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Sorting takes \(O(N \log N)\) and \(O(M \log M)\), and the subsequent greedy processing takes \(O(N + M)\).
• Space complexity: \(O(N + M)\)
  • Memory is needed to store the arrays \(S\) and \(D\).

Implementation Notes

• When reading data from standard input, it is efficient to read all data at once before processing.

• Use the built-in sort() function for sorting. It uses the highly efficient TimSort algorithm.

• By properly managing the pointers \(i\) and \(j\), the matching can be performed in linear time.

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    S = list(map(int, data[2:2+n]))
    D = list(map(int, data[2+n:2+n+m]))
    
    S.sort()
    D.sort()
    
    count = 0
    i = 0
    j = 0
    
    while i < n and j < m:
        if S[i] >= D[j]:
            count += 1
            j += 1
        i += 1
        
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.