백준 7507 : 올림픽 게임

https://www.acmicpc.net/problem/7507

7507번: 올림픽 게임

 

해결 방법 : 그리디

• 끝나는 시간으로 정렬을 한 뒤에 탐욕적으로 참석 가능한 경기를 보면 된다.
• 현재 경기의 end time <= 다음 경기의 start time이면, day, start, end 값을 다음 경기 기준으로 갱신
• 현재 경기와 다음 경기가 서로 다른 day면 고려할 필요 X

import sys
input = sys.stdin.readline

def solution(m, matches):
    answer = 1
    matches.sort(key=lambda x : (x[0], x[2])) # day, end time으로 정렬
    d, s, e = matches[0] # day, start, end
    for i in range(1, m):
        if d != matches[i][0] or e <= matches[i][1]: # 다음 경기 참석 가능
            d, s, e = matches[i] # day, start, end 갱신
            answer += 1

    return answer

if __name__ == '__main__':
    T = int(input())
    for t in range(T):
        m = int(input())
        matches = [tuple(map(int, input().split())) for _ in range(m)]
        result = solution(m, matches)
        print(f'Scenario #{t + 1}:\n{result}\n')