백준 14464 소가 길을 건너간 이유 4 (USACO February 2017 Silver 1번)

문제 링크: https://www.acmicpc.net/problem/14464

14464번: 소가 길을 건너간 이유 4

Binary Search (lower_bound)

소가 A에서 B사이에 길을 건너는데, B를 기준으로 정렬시킨후 A와 B 사이에 있는 가장 작은 T를 찾으면 됨. 한번 찾았으면 그 닭은 더이상 다른소를 도울수 없으므로 multiset에서 지움.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
 
multiset<int> chicken;
vector<pii> cow;
 
bool cmp(pii a, pii b) {
    return a.second < b.second;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int c, n;
    cin >> c >> n;
    for(int i = 0; i < c; i++) {
        int t;
        cin >> t;
        chicken.insert(t);
    }
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        cow.push_back({a, b});
    }
    sort(cow.begin(), cow.end(), cmp);
 
    int ans = 0;
    for(int i = 0; i < n; i++) {
        auto it = chicken.lower_bound(cow[i].first);
        if(it != chicken.end() && *it <= cow[i].second) {
            ans++;
            chicken.erase(it);
        }
    }
 
    cout << ans << '\n';
    return 0;
}