[BOJ 1946] 신입 사원

https://www.acmicpc.net/problem/1946

정렬 후 그리디 적으로 접근을 하면 된다.

n의 제한이 크기 떄문에 완전탑색식의 비교는 안되고 첫번째 성적을 기준으로 정렬을 한 뒤 2번째부터 n번째가지 최대 성적을 갱신해 주는 방식을 사용한다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
int t,n,ans;
 
vector<pair<int,int>> v;
 
int main(){
    scanf("%d" , &t);
    while(t--){
        scanf("%d" , &n);
        for(int i=1;i<=n;i++){
            int a,b;
            scanf("%d%d" , &a,&b);
            v.push_back({a,b});
        }
        sort(v.begin(),v.end());
        
        int maxv = v[0].second;
        ans = 1;
        
        for(int i=1;i<n;i++){
            if(maxv>v[i].second){
                ans++;
                maxv = v[i].second;
            }
        }
        cout <<ans<<endl;
        v.clear();
    }
    return 0;
}