バスに乗れる人数に制限がないことから、一番天井が高いバスに全員を乗せるのが最適です。よって、 \(H\) のうち \(D\) の最大値より大きな値の個数が答えとなります。

計算量は \(O(N+M)\) です。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> d(n);
  for(int i=0; i<n; i++) cin >> d[i];
  int dmax = *max_element(d.begin(), d.end());

  int ans = 0;
  for(int i=0; i<m; i++){
    string s;
    int h;
    cin >> s >> h;
    if(h > dmax){
      ans++;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N, M = map(int, input().split())
D = list(map(int, input().split()))
Dmax = max(D)

ans = 0
for _ in range(M):
  S, H = input().split()
  if int(H) > Dmax:
    ans += 1
print(ans)