CODE FESTIVAL 2014 Easy D - 枕決め

atcoder.jp

典型的な貪欲問題

問題概要
N人の人とM個の枕がある。
N人はそれぞれ以上以下高さの枕が好みである。
それぞれの枕がせいぜい一度しか選べないとき、好みの枕を使用できる人の最大数を求める。

考えたこと
制約からかが見える。とりあえず貪欲で考えてみる。

初めにとの間隔が小さい順にソートして、条件を満たす枕を小さい順に二分探索で探すような処理をする→WA

確かにこれは,
3 3
1 2
1 2
2 3
のケースで落ちる。

終点を固定して、その終点までの最大値を貪欲に求めていけばよさそう。
区間スケジューリングの要領での小さい順にソートして、条件を満たす枕を小さい順に二分探索で探すような処理をする→AC

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  
  int n, m; cin >> n >> m;
  vector<pair<int, int>> vp(n);
  vector<int> a(m);

  REP(i,n){
    int x,y;cin >>x >> y;
    vp[i] = make_pair(y, x); 
  }
  sort(all(vp));
  BIT<int> bit(100010);
  REP(i,m)cin>>a[i], bit.add(a[i], 1);
  int ans = 0;
  REP(i,n){

    int lb = vp[i].second-1, ub = vp[i].first+1;
    int aba = bit.sum(lb+1);
    while(ub-lb>1){
        int mid = (ub+lb)/2;
        if(bit.sum(mid+1)-aba >= 1){
            ub = mid;
        }else{
            lb = mid;
        }
    } 
    if(ub == vp[i].first+1) continue;
    ans++;
    bit.add(ub,-1);
  }
  cout << ans << endl;
  return 0;
}

priority_queueは全く思いつかなかった。実質的にやってることは同じだと思います