Overview

This is a problem of loading as many items as possible onto \(N\) carts using \(N\) items. Each cart can carry at most \(1\) item whose weight does not exceed the cart’s weight capacity, and we need to find the maximum number of items that can be transported.

Approach

This is a classic greedy algorithm problem where we need to think about “which item should be assigned to which cart for an optimal result.”

Let’s consider the following strategy: 1. Look at items in order from lightest to heaviest. 2. Among the carts that can carry that item, use the one with the smallest weight capacity.

Why is this approach optimal? For example, if we deliberately place a light item on a cart with a very large weight capacity, we waste the “room” that could have been used for heavier items that come later. By assigning a “barely sufficient cart” to small items, we save the larger carts for heavier items — this is the smart strategy.

By sorting both the item weights \(W\) and the cart capacities \(C\) in ascending order, we can efficiently perform this “match from the smallest” process.

Algorithm

1. Sort the list of item weights \(W\) and the list of cart capacities \(C\) each in ascending order.
2. Prepare two pointers (\(i\) for items and \(j\) for carts). Both start at \(0\).
3. Repeat the following while \(i < N\) and \(j < N\):
   • If item \(i\) can be loaded onto cart \(j\) (\(W_i \leq C_j\)): A match is made. Increment the count of transportable items by \(1\), and advance both \(i\) and \(j\) by \(1\) to look at the next item and next cart.
   • If item \(i\) cannot be loaded onto cart \(j\) (\(W_i > C_j\)): Cart \(j\) does not have enough capacity. Since item \(i\) is the lightest among the remaining items (with weight \(W_i\) or more), no future item can be loaded onto cart \(j\) either. Therefore, we give up on cart \(j\) and advance only \(j\) by \(1\).
4. The final count is the answer.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the lists takes \(O(N \log N)\).
  • The subsequent two-pointer traversal is \(O(N)\).
  • Overall, the sorting complexity is dominant.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input \(W\) and \(C\).

Implementation Notes

• Since \(N\) can be as large as \(2 \times 10^5\), in Python it is advisable to use fast input methods such as sys.stdin.read().split() rather than input().

• By using the two-pointer technique, we avoid nested loops and efficiently determine the matching.

  Source Code

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nを取得
    n = int(input_data[0])
    
    # 荷物の重さ W と台車の耐荷重 C を取得
    w = list(map(int, input_data[1:n+1]))
    c = list(map(int, input_data[n+1:2*n+1]))
    
    # 昇順にソート
    w.sort()
    c.sort()
    
    # 2ポインタ法を用いて、軽い荷物から順に、
    # それを載せられる最小の耐荷重を持つ台車を割り当てる
    ans = 0
    i = 0 # 荷物のインデックス
    j = 0 # 台車のインデックス
    
    while i < n and j < n:
        if w[i] <= c[j]:
            # 荷物 i を台車 j に載せられる場合
            ans += 1
            i += 1
            j += 1
        else:
            # 荷物 i が台車 j に載らない場合、より大きな台車を探す
            j += 1
            
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.