Python - 공주님의 정원 (2457) 그리디

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

2457번: 공주님의 정원

 

시간 복잡도

 - N이 무한으로 커져도 중첩되어 있는 while문은 N만큼 돌지 않으니 시간복잡도는 O(n)입니다.

 

import sys
input = sys.stdin.readline
n = int(input().strip())
a = []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().strip().split())
    a.append([x1 * 100 + y1, x2 * 100 + y2])
a.sort(key = lambda x : x[0])
st, ed = 301, 0
ans = 0
i = 0
while True:
    if st > 1130 or i == n : break
    
    while i < n and a[i][0] <= st:
        if a[i][1] > ed:
            ed = a[i][1]
        i += 1
    # 꽃이 지는 날짜(ed)보다 늦게 핀다면 break 
    if i < n and a[i][0] > ed : break
    ans += 1
    st = ed

if st <= 1130: print(0)
else : print(ans)