728x90
2457번: 공주님의 정원
첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서,
www.acmicpc.net
분석
N개의 꽃들 중에서 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력
풀이
import sys
input=sys.stdin.readline
n = int(input())
f = []
for i in range(n):
sm,sd,em,ed=map(int, input().split())
f.append([sm*100+sd, em*100+ed])
f.sort()
start = 301 # 시작날
end=0 # 종료날
cnt=0
while f:
if start < f[0][0] or start >= 1201: # 시작 날짜보다 첫꽃이 늦게필 때 / 비교 종료
break
for i in range(len(f)):
now_start, now_end = f[0]
if start >= now_start: # 시작날짜 겹친다면
end = max(end, now_end) # 가장 긴 종료날로 저장
f.remove(f[0])
else:
break
start = end # 현재 종료날을 다음 시작날과 비교하기 위해 target 저장
cnt += 1
if start <1201:
print(0)
else:
print(cnt)
728x90