[BOJ 2457]プリンセスの庭

質問する
[BOJ 2457]プリンセスの庭
N輪の花から2つの条件を満たす花を選択

3月1日~11月30日に1日1本以上開花し、

花の数はなるべく少なく、

構想する
前の花と重なる花の中で一番遅く散る花を選ぶ(グリディ)
選択されていない花は次も選択されていません
コード#コード#

import sys
input = sys.stdin.readline

N = int(input()) #꽃개수<=100,000

# 노트1
# 예를 들어, 한 줄 입력이 1 1 5 31 로 들어오면
# flowers.append((101,531)) 로 저장
flowers = []
for _ in range(N):
    date = list(map(int,input().split()))
    st,en = date[0]*100+date[1],date[2]*100+date[3] 
    flowers.append((st,en))
flowers.sort()

end,tmp,idx,ans = 301,301,0,0
while end<=1130:
    '''
    # 핵심 알고리즘
    # 겹치는 꽃들 중 가장 늦게 지는 꽃 고르기
    # tmp가 갱신되지 못하는 꽃은 다음 번에도 볼 필요없기 때문에
    # idx += 1 해줘도 됨
    '''
    while idx<N and flowers[idx][0]<=end: # 노트2
        tmp = max(tmp,flowers[idx][1])
        idx += 1
    # 겹치는 꽃이 없으면 무조건 답 0
    if tmp==end:
        print(0)
        sys.exit(0)
    end = tmp
    ans += 1
print(ans)

ノート

日付は(月*100+日)として保存され、月末区分は不要です.

while文を使用すると、満足できる条件を簡潔に書くことができます.