Overview

Given treasure chest strengths \(C_i\) and key capabilities \(R_j\), find the maximum number of treasure chests that can be opened using each key at most once. A greedy approach of “processing chests from weakest to strongest, assigning the weakest available key that can open each” achieves the maximum.

Analysis

Key Insight

To open treasure chest \(i\), we need \(C_i \le R_j\). While the number of possible assignments of keys to chests is enormous, the following strategy is optimal:

• Chests with smaller strength are easier to open
• If we use an unnecessarily powerful key to open a chest, we may be unable to open a chest later that truly requires high capability

Therefore: - Process chests in increasing order of strength, and for each, use the weakest key that can open it This is natural and optimal (a strategy that avoids wasting resources).

Why a Naive Approach Fails

For example, naively searching for a usable key for each chest leads to a worst case of \(O(NM)\) (with both up to \(2\times 10^5\), this is far too slow). Solving this as a general maximum matching problem is also too heavy. However, since the condition is the one-dimensional inequality \(C_i \le R_j\), it can be solved with sorting + greedy.

Concrete Example

• Chests: \(C=[2,5,6]\)
• Keys: \(R=[1,5,7]\)

Processing in increasing order: - Chest 2 is opened with key 5 (saving key 7) - Chest 5 is opened with (remaining) key 7 - Chest 6 has no remaining keys Total: 2 chests. If we had used key 7 on chest 2, chest 5 couldn’t be opened, giving only 1 — a worse result.

Algorithm

1. Sort the chest strength array \(C\) in ascending order
2. Sort the key capability array \(R\) in ascending order
3. Prepare two pointers \(i, j\) (\(i\) points to chests, \(j\) points to keys)
4. Repeat the following:
   • If \(R_j \ge C_i\), this key can open this chest, so assign it → Increment the count by 1, advance both \(i\) and \(j\)
   • Otherwise, the key is too weak, and it cannot open any subsequent (stronger) chests either → Advance only \(j\) and try the next key
5. When either is exhausted, stop. The assignment count is the answer.

This method always assigns the weakest available key to the weakest remaining chest, avoiding waste of key capability, and is therefore optimal.

Complexity

• Time complexity: \(O(N\log N + M\log M)\) (dominated by sorting; the scan is \(O(N+M)\))
• Space complexity: \(O(1)\) (constant additional space aside from sorting)

Implementation Notes

• Be sure to sort \(C, R\) in ascending order before scanning with two pointers.

• The condition while i < N and j < M: prevents out-of-bounds access.

• When \(R_j < C_i\), advance the key pointer, not the chest pointer (since this key is useless for all remaining chests as well).

  Source Code

import sys

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

    i = j = 0
    ans = 0
    while i < N and j < M:
        if R[j] >= C[i]:
            ans += 1
            i += 1
            j += 1
        else:
            j += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.