Overview

There are \(N\) packages and \(N\) carts, each given a weight and a load capacity respectively. The goal is to optimally assign packages to carts and find the maximum number of packages that can be transported.

Analysis

This problem is a combinatorial optimization problem of “which package to assign to which cart.” A naive approach would be to try all possible assignments, but the computational complexity would be extremely large (\(N!\) possibilities). Therefore, an efficient method is needed.

A key observation is that a greedy approach works: “process packages from lightest to heaviest, assigning each to the cart with the smallest load capacity that can still accept it.” Specifically:

• Sort the package weights \(W\) in ascending order
• Sort the cart load capacities \(C\) in ascending order

Then, match them in order from the beginning.

The reason this yields an optimal solution is that lighter packages have more available cart options, while heavier packages have fewer carts to choose from, so it is optimal to process lighter packages first.

Let’s look at a concrete example below.

Example:

Package weights: [2, 5, 3] Cart load capacities: [6, 2, 4]

After sorting:

Packages: [2, 3, 5] Carts: [2, 4, 6]

• Package 2 → Cart 2 (OK)
• Package 3 → Cart 4 (OK)
• Package 5 → Cart 6 (OK)

In this way, all packages can be transported.

Conversely, if we try to assign heavier packages first, for example, assigning package 5 to cart 6 might waste carts, leaving remaining lighter packages unable to be loaded onto the remaining carts.

Algorithm

1. Sort the package list \(W\) and the cart list \(C\) each in ascending order.
2. Iterate through both lists from the beginning: if the current package can fit on the current cart, assign it.
3. If assigned, move on to the next package and the next cart.
4. If the package doesn’t fit, skip that cart and check the next one.
5. Repeat this process and count how many packages can be transported.

This is a classic algorithm called the greedy method, and optimality is guaranteed for this problem.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (storage for the input arrays)

Implementation Notes

• sys.stdin.read is used to read input efficiently.
• Two pointers (i, j) are used to simulate the process, ensuring correct index management after sorting.
• Note that in Python, sort() is destructive (it modifies the list in place).

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    W = list(map(int, data[1:N+1]))
    C = list(map(int, data[N+1:2*N+1]))
    
    # 荷物と台車をそれぞれソート
    W.sort()
    C.sort()
    
    # 貪欲法でマッチング
    i = 0  # 荷物のインデックス
    j = 0  # 台車のインデックス
    count = 0
    
    while i < N and j < N:
        if W[i] <= C[j]:
            count += 1
            i += 1
            j += 1
        else:
            j += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

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