[C++] 백준 14464번 - 소가 길을 건너간 이유 4

greedy한 문제였다

단순히 닭이 소의 시간 안에 들어있는지 아닌지를 파악해주면 되는 문제라 쉬워보였지만,

소를 priority queue로 정렬하는데에 있어서 시작시간만을 기준으로 정렬하면 틀리는 문제였다.

priority queue의 정렬 함수를 구현하는 것이 결국 관건이었던 문제이다

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int c, n;
struct comp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		if (a.second != b.second) return a.second > b.second;
		return a.first > b.first;
	}
};
vector<int> chicken;
priority_queue<pair<int, int>, vector<pair<int, int>>, comp> cow;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> c >> n;

	for (int i = 0; i < c; i++) {
		int x; cin >> x;
		chicken.push_back(x);
	}
	sort(chicken.begin(), chicken.end());

	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		cow.push({ a, b });
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		auto current = cow.top();
		for (int j = 0; j < chicken.size(); j++) {
			if (chicken[j] >= current.first && chicken[j] <= current.second) {
				//cout << "닭 " << chicken[j] << endl;
				chicken.erase(chicken.begin() + j);
				ans++;
				break;
			}
		}
		//cout << current.first << " " << current.second << endl;
		cow.pop();
	}

	cout << ans << endl;

	return 0;
}