[파이썬/python] 백준 7507 - 올림픽 게임

문제

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

---

문제 설명

1.  올림픽의 모든 경기의 시작 시간과 종료시간, 날짜가 주어진다.
2. 이 때 볼 수 있는 경기의 최대 개수를 구해라.
   1. 경기를 보던 도중 다른 경기를 보기 위해 경기장을 옮길 수 없다.
   2. 경기장을 이동하는데 걸리는 시간은 없다. 
   3. 경기가 시작된 이후 경기장에 들어갈 수 없다.

 

---

풀이

그리디하게 가장 빠른 날짜부터 경기가 끝나는 시간이 빠른 경기 순서대로 선택하면 될 것이라고 생각했다.

1. 모든 경기의 날짜, 끝나는 시간을 오름차순으로 정렬한다.
2. 모든 경기를 반복문을 통해 탐색한다.
   1. 이전 경기의 종료 시간을 prev에 저장한다.
   2. 현재 경기의 시작 시간이 prev보다 같거나 크다면 prev를 초기화 하고 카운팅한다.

---

코드

import sys
input = sys.stdin.readline

for tc in range(1,int(input())+1):
    m = int(input())
    time = [list(map(int,input().split())) for _ in range(m)]
    time.sort(key = lambda x:(x[0],x[2]))
    cnt = 0
    prev = 0 
    day = 1
    for i in range(m):
        if day < time[i][0]:
            day+=1
            prev = 0
        if time[i][1] >= prev:
            prev = time[i][2]
            cnt+=1
    print("Scenario #"+str(tc)+":")
    print(cnt)
    print()

 

---

시간복잡도

• 정렬하는데 시간복잡도 $O(MlogM)$, 반복문을 탐색할 때 $O(M)$의 시간복잡도가 소요된다.
• 시간복잡도는 약 $O(MlogM + M) = O(M(logM + M))$이다.
• 최악일 때 $M = 5*10^4$이므로 약 $O(5*10^4(log2^{13} + 5*10^4))$