AlgoSpot) MATCHORDER

문제 : https://algospot.com/judge/problem/read/MATCHORDER

한국 팀과 러시아팀의 레이팅이 주어지고 한국팀이 이길수있는 최대 승수를 출력하는 문제입니다.

이 문제는 dp를 이용해서 풀수있지만 그럴경우 시간복잡도가 커지게됩니다.

그러므로 탐욕법을 이용해서 풀었습니다.

이길수있는 경기는 가장 레이팅이 비슷한 선수를 이용해서 이기고 무조건 지는경기라면 가장낮은 레이팅의 선수를 내보내서 최적해를 구합니다.

#include 
#include 
#include 

using namespace std;
vector Rus;
vector Kor;

int N;

int order() {
	int wins = 0;
	multiset Ordered_Kor(Kor.begin(),Kor.end());

	for (int i = 0; i < N; ++i) {
		if (*Ordered_Kor.rbegin() < Rus[i]) continue;
		else {
			++wins;
			Ordered_Kor.erase(Ordered_Kor.lower_bound(Rus[i]));
		}
	}

	return wins;
}

int main() {
	std::ios::sync_with_stdio(false);

	freopen("text.txt", "r", stdin);
	int C;
	int num;

	cin >> C;

	while (C--) {
		cin >> N;

		for (int i = 0; i < N; i++) {
			cin >> num;
			Rus.push_back(num);
		}

		for (int i = 0; i < N; i++) {
			cin >> num;
			Kor.push_back(num);
		}
		
		cout << order() << endl;

		Kor.clear();
		Rus.clear();
	}
	
	return 0;
}