[백준 2457] 공주님의 정원

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

2457번: 공주님의 정원

백준 2457 공주님의 정원 문제입니다.

이 문제는 그리디 문제입니다.

바로 정답을 말하자면 필요한 기간동안 피어있을 수 있는 모든 꽃을 찾은 다음 해당 꽃중 가장 오랫동안 피어있을 수 있는 꽃을 찾으면 됩니다.

이 때 주의해야할 것은 경계가 모호할 수 있으므로 명확히 처리해주는 것이 필요합니다

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static int[] monthDay = {31,28,31,30,31,30,31,31,30,31,30,31};
    public static class Flower implements Comparable<Flower>{
        public int start;
        public int end;

        public Flower (int start, int end){
            this.start = start;
            this.end = end;
        }

        public int compareTo(Flower flower){
            if(start < flower.start) return -1;
            else if(start == flower.start){
                if(end < flower.end) return -1;
                else return 1;
            }
            else return 1;
        }
    }

    static PriorityQueue<Flower> pq = new PriorityQueue<Flower>();

    private static int dateToInteger(int month, int day){
        int dateInt = 0;
        for(int i=0;i<month-1;i++){
            dateInt += monthDay[i];
        }
        dateInt += day;
        return dateInt;
    }
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int startMonth = Integer.parseInt(st.nextToken());
            int startDay = Integer.parseInt(st.nextToken());
            int endMonth = Integer.parseInt(st.nextToken());
            int endDay = Integer.parseInt(st.nextToken());
            int startDateInteger = dateToInteger(startMonth, startDay);
            int endDateInteger = dateToInteger(endMonth, endDay);
            if(startDateInteger >= endDateInteger) continue;
            pq.add(new Flower(startDateInteger, endDateInteger - 1));
        }
        int needMn = dateToInteger(3, 1);
        int needMx = dateToInteger(11, 30);
        int mx = dateToInteger(3, 1);
        int cnt = 0;
        boolean flag = false;
        while(true){
            if(pq.isEmpty() || pq.peek().start > needMn){
                if(!flag) break;
                flag = false;
                cnt++;
                needMn = mx+1;
                if(mx >= needMx) {
                    flag = true;
                    break;
                }
                if(pq.isEmpty()) break;
            }
            Flower flower = pq.poll();
            // System.out.println(flower.start + " " + flower.end);
            mx = Math.max(mx,flower.end);
            flag = true;
        }
        System.out.println(flag?cnt:0);
        
    }
}