Overview

Given the weights of packages \(W_i\) and the load capacities of carts \(C_j\), find the maximum number of “one package + one cart” pairs that can be formed such that the condition \(W_i \le C_j\) is satisfied.

Analysis

This problem looks like a bipartite matching problem where we want to “create as many pairs as possible,” but using a general maximum matching algorithm tends to be expensive. In this case, the condition is only a one-dimensional comparison \(W_i \le C_j\), so it can be solved with a much simpler greedy approach.

The key observations are as follows:

• Lighter packages have more candidate carts they can be loaded on (the constraint is looser).
• Conversely, heavier packages have fewer carts they can be loaded on (they require larger load capacities).

Therefore, - For carts with smaller load capacities, load the lightest available package that fits.
This is the natural approach. Following this rule maximizes the remaining options for future assignments.

Why a Naive Approach Doesn’t Work

For example, if for each cart you naively “search for a package that fits,” the worst case becomes \(O(N^2)\).
Since \(N \le 2 \times 10^5\), \(N^2\) is not practical (TLE).

By sorting and scanning in order, the search can be made linear.

Concrete Example

• Packages: \(W=[2,3,5]\)
• Carts: \(C=[3,4,5]\)

Sort both, then: - Cart with capacity 3: load the lightest package, 2 (success) - Cart with capacity 4: load the next lightest package, 3 (success) - Cart with capacity 5: load the next lightest package, 5 (success)

A total of 3 packages can be transported.

If we had loaded package 3 onto the cart with capacity 3, then package 5 wouldn’t fit on the cart with capacity 4, resulting in failure. This shows the importance of the greedy selection strategy.

Algorithm

1. Sort the package weight array \(W\) and the cart load capacity array \(C\) in ascending order.
2. Initialize a pointer \(i\) at 0, representing the position of “the lightest unused package we want to load next.”
3. Iterate through the carts in ascending order of load capacity, letting cap be the current cart’s capacity.
   • If \(i < N\) and \(W[i] \le cap\), then this package can be loaded onto this cart, so:
     • Increment the answer by 1
     • Advance \(i\) by 1 (move to the next lightest package)
   • Otherwise, no unused package can be loaded onto this cart (since the current package is the lightest remaining and it doesn’t fit), so skip this cart.
4. The counted number is the maximum number of packages that can be transported.

The key point is “for each cart, if a package can be loaded, assign the lightest unused package.” This preserves carts with larger load capacities for heavier packages.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting \(W\) and \(C\); the scan is \(O(N)\))
• Space complexity: \(O(1)\) (constant additional space excluding the input arrays; internal space for sorting depends on the language implementation)

Implementation Notes

• Sort both arrays first, then process carts in ascending order.

• Manage the package side with index \(i\), advancing \(i\) only on a successful assignment (a so-called two-pointer technique).

• When \(W[i] > cap\), even the lightest package cannot fit on that cart, so all subsequent (heavier) packages won’t fit either. Therefore, simply give up on that cart and move to the next one.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    W = list(map(int, input().split()))
    C = list(map(int, input().split()))

    W.sort()
    C.sort()

    i = 0
    ans = 0
    for cap in C:
        if i < N and W[i] <= cap:
            ans += 1
            i += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.