[BOJ][20440] 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 - JAVA

링크 :  https://www.acmicpc.net/problem/20440

 

풀이 링크 : https://coder-in-war.tistory.com/entry/BOJ-JAVA20440-%EB%8B%88%EA%B0%80-%EC%8B%AB%EC%96%B4-%EC%8B%AB%EC%96%B4-%EB%84%88%EB%AC%B4-%EC%8B%AB%EC%96%B4-%EC%8B%AB%EC%96%B4-%EC%98%A4%EC%A7%80%EB%A7%88-%EB%82%B4%EA%B2%8C-%EC%B0%9D%EC%A0%81%EB%8C%80%EC%A7%80%EB%A7%88-1

[ BOJ ][JAVA][20440] 니가 싫어 싫어 너무 싫어 싫어 오지마 내게 찝적대지마 - 1

 

- 풀이 보고 품

- 우선순위 큐 문제

- 초당 cnt 하게되면 21억번 max일 때 시간 초과

- 따라서 새로운 시간이 add 될 때, poll 될 때 체크를 해주면 10,000 번 안에서 끝나게 된다.

 

 

 

import java.util.*;

public class Solution {
    static class Mogi {
        int startTime;
        int endTime;

        public Mogi(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }

        public int getStartTime() {
            return startTime;
        }

        public int getEndTime() {
            return endTime;
        }
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        ArrayList<Mogi> mogis = new ArrayList();
        for (int i = 0; i < N; i++) {
            int st = sc.nextInt();
            int et = sc.nextInt();
            mogis.add(new Mogi(st, et));
        }

        mogis.sort(Comparator.comparing(Mogi::getEndTime).thenComparing(Mogi::getStartTime));

        PriorityQueue<Integer> q = new PriorityQueue<>();
        q.add(mogis.get(0).endTime);

        int cnt = 1;

        int s = mogis.get(0).startTime;
        int e = mogis.get(0).endTime;
        for(Mogi mogi: mogis) {
            System.out.println(mogi.startTime + " : " + mogi.endTime);
        }

        for (int i = 1; i < N; i++) {

            while (!q.isEmpty() && q.peek() < mogis.get(i).startTime) { // 가장 빠른 endtime = q.peek() < starttime 작다 : 이미 지나갔다
                q.poll();
            }

            if(!q.isEmpty() && q.peek() == mogis.get(i).startTime) { // 가장 빠른 endTime == startime 이라면 길이 늘려줘 
                if (q.peek() == e) {
                    e = mogis.get(i).endTime; // endTime은 i의 endTime으로 해줘
                }
                q.poll();
            }

            q.add(mogis.get(i).endTime);
            if(q.size() > cnt) {
                cnt = q.size();
                s = mogis.get(i).startTime;
                e = q.peek();
            }
        }

        System.out.println(cnt);
        System.out.println(s + " " + e);

    }
}