CODE FESTIVAL 2014 Middle B - 枕決め
解法
貪欲法で解きます。
右端ができるだけ左にあるものから採用するほうが最適です。
ということで, アルゴリズム的には以下のようなことをやります。
・a[i] が x[cur] 以下のもののうち, まだ使っていないものを全部列挙する
・これらのうち, y[cur] が一番小さいものがあればそれを a[i] と対応させて ans++
とこんな感じです。単純にやると TLE かもしれないので priority_queue を使いました。
const int MAXN = 100100; pii P[MAXN]; int A[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) cin >> P[i].first >> P[i].second; for (int i = 0; i < m; i++) cin >> A[i]; sort(P, P+n); sort(A, A+m); int cur = 0, ans = 0; priority_queue<pii, vector<pii>, function<bool(pii, pii)>> que([](pii lhs, pii rhs){return lhs.second > rhs.second;}); for (int i = 0; i < m; i++) { // P[j].first が a[i] 以下のものを入れていく while (cur < n && P[cur].first <= A[i]) { que.push(P[cur]); cur++; } // a[i] より右側にあるものの中で一番左側にあるやつを探す while (!que.empty()) { pii p = que.top(); que.pop(); if (A[i] <= p.second) { ans++; break; } } } cout << ans << endl; return 0; }