Overview

Given the weights of packages and the load capacities of carts, where each cart can carry at most one package, find the maximum number of packages that can be transported.

Analysis

This problem can be thought of as a maximum matching problem where each package is assigned to a cart with sufficient load capacity. A naive approach would try all possible assignments, but since \(N\) can be as large as 200,000, an \(O(N^2)\) time complexity would not meet the time limit.

The key observation is that in an optimal assignment, it is more efficient to “assign lighter packages to carts with smaller load capacities.” Assigning heavier packages requires carts with larger load capacities, but lighter packages can be carried even by carts with smaller load capacities. Therefore, carts with larger load capacities should be reserved for heavier packages.

Algorithm

1. Sort both the list of package weights \(W\) and the list of cart load capacities \(C\)
2. Process packages from lightest to heaviest, assigning each to the cart with the smallest sufficient load capacity
3. Specifically, for package \(i\), find the smallest \(j\) such that \(C_j \geq W_i\)
4. If a matching cart is found, increment the count and move to the next cart
5. Repeat this for all packages

This greedy approach allows us to transport the maximum number of packages. By sorting, we can find the optimal cart for each package in linear time.

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for sorting, \(O(N)\) for the greedy assignment)
• Space complexity: \(O(N)\) (arrays to store the input data)

Implementation Notes

• The greedy matching after sorting is the key

• Manage the cart index j outside the loop, and for each package, search for the smallest cart that satisfies the condition

• Break out of the loop immediately when there are no more carts available, to avoid unnecessary processing

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    W = list(map(int, data[1:1+n]))
    C = list(map(int, data[1+n:1+2*n]))
    
    W.sort()
    C.sort()
    
    count = 0
    j = 0
    for i in range(n):
        while j < n and W[i] > C[j]:
            j += 1
        if j >= n:
            break
        count += 1
        j += 1
        
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.