[Inflearn] PS - 002

문제 출처 : inflearn <파이썬 알고리즘 문제풀이(코딩테스트 대비)>

씨름 선수(그리디)

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습
니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“다른 모든 지원자와 비교하여 키와 몸무게 중 적어도 하나는 다른 지원자보다 키가 크거나
몸무게가 많이 나가는 지원자만 뽑기로 했습니다.”
A 지원자가 다른 모든 지원자와 비교하여 키와 몸무게가 모두 작거나 가벼운 경우가 한 번이
라고 있다면 A지원자를 뽑지 않는다는 것입니다.

▣ 입력설명
첫째 줄에 지원자의 수 N(5<=N<=50)이 주어집니다.
두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다. 각 선수의 키와 몸무게는 모두
다릅니다.

▣ 출력설명
첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요.

▣ 입력예제 1
5
172 67
183 65
180 70
170 72
181 60

▣ 출력예제 1
3

풀이

'''
접근
1. 모든 선수들의 정보를 (키, 몸무게)로 변수에 할당한다.
2. 할당한 변수 중 키의 역순으로 정렬한다.
3. 이후 몸무게만 비교하면 된다.
'''

import sys
sys.stdin=open("input.txt", "r")
n = int(input())
body = []

for i in range(n):
    h, w = map(int, input().split())
    body.append((h, w))
body.sort(reverse=True)

wei = 0
cnt = 0
for h, w in body:
    if w > wei:
        cnt += 1
        wei = w

print(cnt)