📝 문제 정보#
🧐 관찰 및 접근#
- 소에 대해서는 끝나는 시간이 가장 빠른 소를, 닭에 대해서는 가장 $T$가 빨리 오는 닭을 쓰는 그리디가 성립한다.
- 이를 구현하는 방법은 여러가지가 있겠지만, 여기서는 multiset과 이분탐색을 이용하겠다.
💻 풀이#
- 코드 (C++):
void solve(){
int C, N; cin >> C >> N;
multiset<int> chicken;
rep(i, 0, C){
int x; cin >> x;
chicken.insert(x);
}
vector<pii> cow(N);
rep(i, 0, N) cin >> cow[i].first >> cow[i].second;
sort(all(cow), [](pii a, pii b){
return a.second < b.second;
});
int ans = 0;
for(auto [s, e]: cow){
auto it = chicken.lower_bound(s);
if(it != chicken.end() && *it <= e){
ans++;
chicken.erase(it);
}
}
cout << ans << '\n';
}