[Greedy] 1946번 - 신입 사원(41일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline

for T in range(int(input())):
  #지원자 수  
  N = int(input())
  #합격 가능한 지원자 수
  cnt = 1
  #지원자들의 서류, 면접 점수 저장 list
  member = []
  #자원자들의 서류, 면접 점수 저장
  for i in range(N):
    docu, inter = map(int, input().split())
    member.append([docu, inter])
  #서류 점수에 따라 정렬
  member.sort(key = lambda x: x[0])
  #가장 낮은 면접 점수 저장
  mem_min = member[0][1]
  #서류 점수 기준으로 정렬된 모든 지원자에 대해 면접 점수 최소값 업데이트
  for j in range(1,N):
    #해당 지원자의 면접 점수가 면접 점수 최소값보다 낮을 시
    if(member[j][1] < mem_min):
      #합격가능한 지원자 수 추가
      cnt += 1
      #최소값 업데이트
      mem_min = member[j][1]
  #합격 가능한 지원자 수 출력
  print(cnt)

#인사이트
#귀납적 접근으로 정답 로직을 도출한 것까지는 유효
#최대 합격자: 서류 점수가 더 높지만, 면접 점수는 더 낮은 지원자들이 합격 가능
#보다 신중하게 끝까지 로직을 고민했어야 함