신입 사원

풀이

 문제 유형은 그리디, 정렬이다. 먼저 서류 순위를 기준으로 오름차순 정렬한다.

1 4
2 3
3 2
4 1
5 5

 서류 순위가 1위, 면접 순위가 4위인 지원자는 무조건 채용해야 하므로 면접 순위 4를 기준으로 잡고 아래 지원자들의 면접 순위와 비교해서 기준값보다 작으면 counting하고 기준값 reset, 기준값보다 크면 skip 하면 된다.

import sys
T = int(input())
result = []
for i in range(T):
    N = int(input())
    data = []
    for i in range(N):
        data.append(list(map(int, sys.stdin.readline().split())))
    data.sort(key=lambda x:x[0])
    count = 1
    top = data[0][1]
    for i in range(1, N):
        if data[i][1] < top:
            top = data[i][1]
            count += 1
    result.append(count)

for x in result:
    print(x)

시간복잡도 : O(TNlogN)