各お客さんがどのチケットを買うかを愚直に調べていると、お客さんごとに \(\Theta(M)\) 、全体で \(\Theta(NM)\) かかり、実行時間制限に間に合わせるのは困難です。

\(G\) を予めソートしておきます。これにより、各お客さんがどのチケットを選ぶかを、二分探索により \(O(\log M)\) で求めることができます。あとは、各チケットを既に販売した枚数を保持しておくことで、 \(O(N\log M+M)\) 時間でこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,m,k;
  cin >> n >> m >> k;
  vector<long long> s(n), g(m);
  for(int i=0; i<n; i++) cin >> s[i];
  for(int i=0; i<m; i++) cin >> g[i];
  sort(g.begin(), g.end());

  vector<int> count(m);
  int ans = 0;
  for(int x=0; x<n; x++){
    int i = upper_bound(g.begin(), g.end(), s[x]) - g.begin() - 1;
    if(i >= 0 && count[i] < k){
      count[i]++;
      ans++;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

import bisect
N, M, K = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
G.sort()

count = [0] * M
ans = 0
for s in S:
  i = bisect.bisect_right(G, s) - 1
  if i >= 0 and count[i] < K:
    count[i] += 1
    ans += 1

print(ans)