백준 20440[자바] java 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

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

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

 

▶문제

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

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

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

---

▶입력

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

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

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

---

▶출력

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

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

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

---

▶해설

이전에 풀었던 강의실 배정과 매우 비슷한 문제여서 설명은 생략하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Time implements Comparable<Time> {
    long start;
    long end;

    public Time(long start, long end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Time o) {
        if (this.end < o.end) {
            return -1;
        } else if (this.end == o.end) {
            if (this.start < o.start) {
                return 1;
            } else {
                return -1;
            }
        } else {
            return 1;
        }
    }
}

public class Main {
    static int n;
    static long[][] arr;
    static long a, b;
    static PriorityQueue<Time> queue = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new long[n][2];

        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            arr[i][0] = Long.parseLong(s[0]);
            arr[i][1] = Long.parseLong(s[1]);
        }

        Arrays.sort(arr, (a, b) -> {
            if (a[0] <= b[0]) {
                return -1;
            } else {
                return 1;
            }
        });
        int max = 0;
        for (int i = 0; i < n; i++) {
            while (!queue.isEmpty() && arr[i][0] > queue.peek().end) {
                queue.poll();
            }
            if(!queue.isEmpty() && arr[i][0] == queue.peek().end){
                if(queue.peek().end==b){
                    b = arr[i][1];
                }
                queue.poll();
            }
            queue.add(new Time(arr[i][0], arr[i][1]));
            if(queue.size()>max){
                max = queue.size();
                a = arr[i][0];
                b = queue.peek().end;
            }
        }
        System.out.println(max);
        System.out.println(a + " " + b);
    }
}