[백준] 1946번 신입사원 (그리디 알고리즘)

-문제

1) 서류성적으로 오름차순 정렬 

2) 면접성적이 1등인 사람의 서류 성적까지만 탐색한다.

3) 앞의 사람보다 면접성적 등수가 낮으면 카운트++, max값 갱신한다.

 

1 4 (max = 4, cnt =1)

2 5 

3 6

4 2 (max = 2, cnt =2)

5 7

6 1 (max = 1, cnt =3)

----------------

7 3

 

 

-코드

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
	int t, n;
	scanf("%d", &t);

	for (int i = 0; i < t; i++)
	{
		scanf("%d", &n);
		vector<pair<int,int> > a(n);
		int mf = 0, ms =0, res=0, min=0;
		for (int j = 0; j < n; j++)
		{
			scanf("%d %d", &a[j].first, &a[j].second);
			if (a[j].second == 1) mf = a[j].first;
		}
		
		sort(a.begin(),a.end());
		min = a[0].second;
		res = 1;
		for (int j = 1; j < mf; j++)
		{
			if (a[j].second > min) continue;
			min = a[j].second;
			res++;
		}

		printf("%d\n", res);
	}

	return 0;
}