CODE FESTIVAL 2014 Middle B - 枕決め

問題

code-festival-2014-morning-middle.contest.atcoder.jp

解法

貪欲法で解きます。

右端ができるだけ左にあるものから採用するほうが最適です。

ということで, アルゴリズム的には以下のようなことをやります。

・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;
}