以下のような貪欲法が成り立ちます。

• 配達員・荷物を混ぜて、(配達員が持てる / その荷物自身の)重さの降順に並べる。
  • 同じ重さの場合は配達員が先に来るようにする。
• その後、並べた列に対して以下を行う。
• 待機中の配達員の人数 \(h=0\) と初期化する。
• 配達員が出てきた場合、 \(h\) に \(1\) 加算する。
  • この配達員は、これ以降に出てくる荷物に限り、それらをどれでも \(1\) つ運ぶことができることに注意する。
• 荷物が出てきた場合、 \(h>0\) である場合に限り \(h\) から \(1\) 減算し答えに \(1\) 加算する(配達員を適当に \(1\) 人選びその荷物を運ばせることに対応する)。 \(h=0\) である時その荷物を運ぶことはできない。

こうすることで配達員を最大限活用できます。

本解法の時間計算量は \(O((N+M) \log (N+M))\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int N,M;
  cin >> N >> M;
  vector<pi> vp;
  for(int i=0;i<N;i++){
    int S;
    cin >> S;
    vp.push_back({S,1});
  }
  for(int i=0;i<M;i++){
    int D;
    cin >> D;
    vp.push_back({D,0});
  }
  sort(vp.rbegin(),vp.rend());
  int h=0,ans=0;
  for(auto &nx : vp){
    if(nx.second==1){
      h++;
    }
    else if(h>0){
      h--; ans++;
    }
  }
  cout << ans << "\n";
  return 0;
}