백준(BOJ) 1946 신입 사원(Python)

문제 내용

 

그리디 문제.

먼저 서류 성적을 기준으로 입력값을 오름차순 정렬한다.

신입 사원이 선발되기 위해서는 자신보다 서류 성적이 높은 사원 중 한 명 이상 면접 성적이 더 높아야 하므로, 리스트의 처음부터 면접 성적의 최솟값을 갱신하며 현재 면접자의 면접 성적과 비교하면 된다.

 

코드는 다음과 같다.

 

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

t=int(input())
for i in range(t):
    n=int(input())
    L=[list(map(int,input().split())) for i in range(n)]
    L.sort()
    L=deque(L)
    ans=0
    k=100001
    while L:
        a,b=L.popleft()
        if b<k:
            ans+=1
            k=min(k,b)
    print(ans)