Overview

Given \(N\) packages and \(N\) carts, where a package can be loaded onto a cart only if the package’s weight does not exceed the cart’s weight capacity, this is a matching problem to find the maximum number of packages that can be transported.

Analysis

Key Insight: Greedy Approach is Optimal

First, trying all possible pairings of packages and carts in a brute-force manner results in \(O(N!)\) combinations, which is far too slow given that \(N\) can be up to \(2 \times 10^5\).

Here is the crucial observation:

Lighter packages are easier to load (they can fit on more carts), so it is optimal to process packages from lightest to heaviest and assign each to the cart with the smallest sufficient capacity.

This is intuitively understandable. Carts with large weight capacities are “precious resources” — they may be the only ones that can handle heavy packages. If we use a large-capacity cart for a light package, we risk leaving a heavy package with no available cart.

Concrete Example

Package weights: \([2, 5, 8]\), Cart capacities: \([3, 6, 7]\)

• After sorting: \(W = [2, 5, 8]\), \(C = [3, 6, 7]\)
• Package \(2\) → Cart \(3\) (can load ✓)
• Package \(5\) → Cart \(6\) (can load ✓)
• Package \(8\) → Cart \(7\) (cannot load ✗)
• Result: 2 packages

If we had loaded package \(2\) onto cart \(6\), then package \(5\) would go on cart \(7\), and package \(8\) still couldn’t be loaded — the result is the same 2 packages. However, using smaller carts first avoids waste and is always optimal.

Algorithm

1. Sort the package weights \(W\) in ascending order
2. Sort the cart capacities \(C\) in ascending order
3. Use Two Pointers to scan through both arrays:
   • Pointer \(i\) refers to carts, pointer \(j\) refers to packages
   • Iterate through carts in order. If the current package \(j\) can be loaded onto cart \(i\) (\(W[j] \leq C[i]\)), match them, increment the count, and advance to the next package \(j+1\)
   • If the package cannot be loaded, try the next larger cart \(i+1\)
4. The count is the answer

This greedy approach corresponds to the strategy of “matching light packages to carts with small capacities first.”

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting; the scanning phase is \(O(N)\))
• Space complexity: \(O(N)\) (for storing the sorted arrays)

Implementation Notes

• Since the algorithm simply performs a linear scan with two pointers after sorting, the implementation is very straightforward

• Note that pointer \(j\) (package side) advances only when a match is made, while pointer \(i\) (cart side) advances every iteration. This ensures that for each cart, we attempt to load the lightest unassigned package

• Using sys.stdin.read() to read all input at once allows the solution to run efficiently even in Python

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    W = sorted(int(input_data[i+1]) for i in range(N))
    C = sorted(int(input_data[i+1+N]) for i in range(N))
    
    count = 0
    j = 0
    for i in range(N):
        if j < N and W[j] <= C[i]:
            count += 1
            j += 1
    
    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.