Overview

Given \(N\) treasure chests and \(M\) keys, where a key can open a chest if its unlocking power is greater than or equal to the lock’s strength, find the maximum number of treasure chests that can be opened. Each key can only be used once.

Analysis

Key Insight

This problem is a type of matching problem. We want to match keys to treasure chests in a one-to-one correspondence to open as many chests as possible.

Issues with the Naive Approach

Trying all combinations of keys and treasure chests would result in \(O(N \times M)\) or even worse time complexity. When \(N, M\) can be up to \(2 \times 10^5\), this could result in TLE.

Solution Strategy: Greedy Algorithm

The optimal approach is a greedy algorithm: “Process chests from weakest to strongest, and for each chest, use the weakest available key that can open it.”

Why is this correct?

Intuitive Explanation: - Strong keys can open both weak and strong chests - they are “all-rounders” - Weak keys can only open weak chests - they are “specialists” - It’s better to use “specialists” for weak chests and save “all-rounders” for later

Concrete Example: - Chest strengths: \([10, 50]\) - Key powers: \([30, 60]\)

If we open the weak chest (strength 10) with the strong key (power 60), we won’t have a key left to open the strong chest (strength 50). If we open the weak chest with the weak key (power 30), we can also open the strong chest with the strong key, opening 2 chests total.

Algorithm

1. Sort the chest lock strengths \(C\) in ascending order
2. Sort the key unlocking powers \(R\) in ascending order
3. Process chests from weakest to strongest
4. For each chest, use “the smallest unused key that can open this chest”
5. Count the number of opened chests

Chests (sorted): [10, 50, 80]
Keys (sorted):   [30, 40, 60]

Chest 10 → Open with key 30 ✓
Chest 50 → Key 40 cannot be used (40<50), open with key 60 ✓
Chest 80 → No remaining keys ✗

Answer: 2 chests

Complexity

• Time Complexity: \(O(N \log N + M \log M)\)

  • Sorting chests: \(O(N \log N)\)
  • Sorting keys: \(O(M \log M)\)
  • Matching process: \(O(N + M)\) (each element is visited at most once)

• Space Complexity: \(O(N + M)\)

  • Storing the lists of chests and keys

Implementation Notes

1. Looks like a nested loop but runs in linear time

   • key_idx only increases and never goes back
   • The outer loop runs \(N\) times, and the inner while executes at most \(M\) times in total
   • Therefore, the overall complexity is \(O(N + M)\)

2. Key index management

   • Once a key is used, it cannot be reused, so key_idx is never decremented
   • Even if a chest cannot be opened, keys weaker than the current one won’t be usable for future chests either, so key_idx doesn’t need to be reset

Source Code

def solve():
    N, M = map(int, input().split())
    C = list(map(int, input().split()))
    R = list(map(int, input().split()))
    
    # Sort the chest lock strengths and key unlocking powers
    C.sort()
    R.sort()
    
    # Greedy: Process chests from weakest, use the weakest available key that can open it
    count = 0
    key_idx = 0
    
    for box_strength in C:
        # Find a key that can open this chest (first key where R[key_idx] >= box_strength)
        while key_idx < M and R[key_idx] < box_strength:
            key_idx += 1
        
        if key_idx < M:
            # Found a key that can open the chest
            count += 1
            key_idx += 1
    
    print(count)

solve()

---

This editorial was generated by claude4.5opus.