[BOJ] 1946 신입사원

Greedy

• 중요한 것은 각 숫자별로 '최저값'을 어떻게 설정하는가이다.
• 당연히 1등부터 점수가 있으니까 1등이 제일 최저값이지만, 1등이라고 해서 모두 [1, 1] 형식인 것은 아니다
• 그러므로 한 분야의 1등을 정한 뒤 나머지 부분의 최저값을 계속 갱신해 나가는 것이 이번의 할 일이다(다른 쪽의 1등이 나올 때까지)

import sys
sys.stdin = open('input.txt')
T = int(input())
for _ in range(T):
    N = int(input())
    count = 0
    candidate = [list(map(int, input().split())) for _ in range(N)]
    # 한 분야의 1등을 정하기 위해 정렬한다(이 경우는 1차 시험에서 1등한 사람의 기준이다).
    candidate.sort(key=lambda x:x[0])
    # 답에 우선 1차 시험 1등을 넣어 놓는다.
    answer = [candidate[0]]
    for i in range(1, N):
    	# 1차 시험 1등의 각각의 점수보다 같거나 큰 사람을 계속 더해나간다. 
        # 그러다 보면 각 시험의 최고점(1등)이 가진 다른 부분의 시험 점수를 가진 사람들이 뽑혀나가게 되고,
        # 그 사람들이 뽑힐 수 있는 최저점이 되어 간다.
        if candidate[i][0]<=answer[-1][0] or candidate[i][1]<=answer[-1][1]:
            answer.append(candidate[i])
    print(len(answer))