Overview

There are \(N\) treasure chests (with strength \(C_i\)) and \(M\) keys (with ability \(R_j\)). A key can unlock a treasure chest if the key’s ability is greater than or equal to the chest’s strength. Given the condition that each key can only be used once, the problem asks for the maximum number of treasure chests that can be opened.

Approach

The key point of this problem is to think about “which key should be assigned to which treasure chest most efficiently.”

First, let’s consider the treasure chests in order from the lowest strength (easiest to open). When opening a particular chest, if there are multiple keys capable of opening it, the best strategy is to use the one with the lowest ability among the keys that can open that chest. This is because it’s better to save higher-ability keys for opening stronger chests that may appear later.

Conversely, when focusing on a particular key, any chest that this key cannot open obviously cannot be opened by any subsequent keys with even lower ability.

This approach of “making the best choice at each step” is called a Greedy Algorithm. By sorting both the chest strengths and key abilities in ascending order, we can efficiently simulate this greedy strategy.

Algorithm

1. Sort the list of chest strengths \(C\) in ascending order.
2. Sort the list of key abilities \(R\) in ascending order.
3. Set two pointers (chest_ptr pointing to chests and key_ptr pointing to keys) to the beginning (0).
4. Repeat the following operations until either pointer reaches the end:
   • If R[key_ptr] >= C[chest_ptr]:
     • The key can open the chest.
     • Increment the count of opened chests by 1, and advance both pointers by 1 to examine the next chest and next key.
   • Otherwise (the key’s ability is insufficient):
     • The current key cannot open the current chest (nor any subsequent stronger chests).
     • Give up on this key and advance only key_ptr by 1 to try the next key with higher ability.
5. Output the final count.

Complexity

• Time Complexity: \(O(N \log N + M \log M)\)
  • Sorting the chests and keys takes \(O(N \log N)\) and \(O(M \log M)\) respectively.
  • The subsequent traversal with two pointers is \(O(N + M)\).
  • Overall, the sorting complexity dominates.
• Space Complexity: \(O(N + M)\)
  • This is the memory required to store the input lists of chests and keys.

Implementation Notes

• Fast I/O: Since \(N, M\) can be as large as \(2 \times 10^5\), which is relatively large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Importance of Sorting: To apply the greedy algorithm, the data must be sorted in ascending order. Forgetting to sort will make it impossible to find optimal pairings, resulting in a wrong answer (WA).

  Source Code

import sys

def main():
    # 全ての入力を一度に読み込み、空白で分割してリストにします。
    # これにより、大量の入力データを高速に処理することが可能です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 宝箱の個数 N と 鍵の本数 M を取得します。
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各宝箱の錠前の強度 C と 各鍵の開錠能力 R をリストとして取得します。
    C = list(map(int, input_data[2:2+N]))
    R = list(map(int, input_data[2+N:2+N+M]))
    
    # 強度と能力をそれぞれ昇順にソートします。
    # 貪欲法（Greedy Algorithm）を適用するためにソートが必要です。
    C.sort()
    R.sort()
    
    chest_ptr = 0  # 宝箱を指すポインタ
    key_ptr = 0    # 鍵を指すポインタ
    opened_chests = 0  # 開けることができた宝箱の数
    
    # 2つのポインタを用いて、可能な限り多くの宝箱を鍵に割り当てます。
    while chest_ptr < N and key_ptr < M:
        if R[key_ptr] >= C[chest_ptr]:
            # 現在の鍵で現在の宝箱を開けることができる場合
            # このペアを確定させ、次の宝箱と次の鍵へ進みます。
            opened_chests += 1
            chest_ptr += 1
            key_ptr += 1
        else:
            # 現在の鍵が現在の宝箱に対して弱すぎる場合
            # 宝箱はソートされているため、この鍵はこれ以降のどの宝箱も開けられません。
            # したがって、より能力の高い次の鍵を試します。
            key_ptr += 1
            
    # 最大の宝箱の個数を出力します。
    print(opened_chests)

if __name__ == '__main__':
    main()

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