백준 19598 최소 회의실 개수 java

1. 문제에 대하여 📦

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

2. 코드가 나오기까지 🛠️

1. (시작 시간, 끝 시간)을 멤버로 가지는 클래스를 만든다.
   해당 클래스에 대하여 끝시간 오름차순 우선순위 큐 만들기 -> 우선순위 큐가 강의실 역할을 하고, 우선순위 큐의 사이즈가 강의실 개수임.

2. 입력 받아사 (시작 시간, 끝시간) 객체로 만들고 시작 시간 오름차순 정렬 (시간 순으로 차례대로 보기 위해)

3. 정렬한 리스트에서 차례대로 꺼내서 다음을 진행
1. 큐가 비어져 있으면 그냥 넣기
2. 큐가 안 비어져 있으면 큐의 peek() 강의의 끝시간과 현재 조회 중인 강의의 시작시간 비교
1. 만약 peek() 끝 시간이 현재 조회 중인 시작 시간보다 빠르다면 (강의실에 강의가 먼저 끝난다면) 그렇지 않을 때까지 poll()
2. peek()의 끝 시간이 현재 조회 중인 시작 시간보다 느리다면( 제일 빠르게 끝나는 강의도 현재 시작하려는 강의보다 늦게 끝남) -> 큐에 넣기 (새로운 강의실 선정)

(1) 시간복잡도 분석 ⏳

• 강의 시작 시간 순 정렬: $O(N \log{N})$

• 강의 하나씩 순회하며 큐에 넣거나 뺴기:$O(N \times \log{N})$

3. 코드 🌐

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

// 19598번 최소 회의실 개수
public class Main {
    static class Lecture {
        int start;
        int end;

        public Lecture(int start, int end){
            this.start = start;
            this.end = end;
        }
        @Override
        public String toString(){
            return String.format("(%d, %d)", this.start, this.end);
        }    }    static int N;
    static ArrayList<Lecture> list = new ArrayList<>();
    static PriorityQueue<Lecture> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.end));
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int max = 0;
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            list.add(new Lecture(start, end));
        }        list.sort(Comparator.comparingInt(a -> a.start));
        for(int i = 0; i < list.size(); i++){
            Lecture now = list.get(i);
            if(pq.isEmpty()) pq.add(now);
            else {
                while(!pq.isEmpty() && now.start >= pq.peek().end) pq.poll();
                pq.add(now);
            }            max = Math.max(max, pq.size());
        }        System.out.printf("%d",max);
    }
}

4. 트러블 슈팅 or 배운 점📝