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

www.acmicpc.net/problem/20440

20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	1024 MB	240	92	71	41.040%

문제

🎵니가 싫어 싫어 너무 싫어 싫어 오지마 내게 찝쩍대지마🎵 - 유자, 모기송 中

모기를 싫어하는 지동이는 어느 날 문득 자신의 방에 모기가 가장 많이 있는 시간대가 언제인지 궁금해졌다. 다행히 지동이 방은 최첨단 시스템이 갖춰져 있어 어떤 모기가 방에 언제 입장했고 언제 퇴장했는지를 기록할 수 있다.

지동이를 도와 모기들의 방 입장, 퇴장 시각이 주어졌을 때 모기들이 가장 많이 있는 시간대와 해당 시간대에 모기가 몇 마리가 있는지 구하는 프로그램을 만들어보자.

입력

첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다.

다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 *TX이 주어진다. (0 ≤ *TE < TX ≤ 2,100,000,000)

모기는 *[TE, Tx)*동안 존재한다.

출력

첫째 줄에 지동이 방에 모기가 가장 많이 있는 시간대의 모기 마릿수를 출력한다.

지동이 방에 모기가 가장 많이 있는 시간대의 연속 구간 전체를 *[TEm, TXm)*이라고 할 때,

둘째 줄에 TEm, TXm을 공백으로 구분하여 출력한다. 단, 여러 가지 방법이 있으면 가장 빠른 시작 시각을 기준으로 출력한다.

예제 입력 1

3
2 16
4 6
6 10

예제 출력 1

2
4 10

예제에 따른 모기의 존재 시간을 막대 그림으로 나타내면 위와 같다.

모기가 가장 많은 시간대의 연속 구간은 [4, 10) 이고 해당 시간대의 모기의 수는 2마리이다.

코드

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

public class p20440 {
    static class Time {
        int s, e;
        public Time(int s, int e) {
            this.s = s;
            this.e = e;
        }
    }
    static int n;
    static Time[] time;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        time = new Time[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            time[i] = new Time(start, end);
        }
        Arrays.sort(time, new Comparator<Time>(){
            @Override
            public int compare(Time o1, Time o2) {
                if (o1.s == o2.e) {
                    return o1.e - o2.e;
                }
                return o1.s - o2.s;
            }
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(time[0].e);
        int cnt = 1;
        int s = time[0].s;
        int e = time[0].e;

        for (int i = 1; i < n; i++) {
            while (!pq.isEmpty() && pq.peek() < time[i].s) {
                pq.poll();
            }
            if (!pq.isEmpty() && pq.peek() == time[i].s) {
                if (pq.peek() == e) {
                    e = time[i].e;
                }
                pq.poll();
            }

            pq.add(time[i].e);
            if (pq.size() > cnt) {
                cnt = pq.size();
                s = time[i].s;
                e = pq.peek();
            }
        }
        System.out.println(cnt);
        System.out.println(s + " " + e);

    }
}