[Algorithm] Greedy 알고리즘 _ 강의실 배정

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

public class Main {

    public static class Lecture implements Comparable<Lecture> {
        int start;
        int end;

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

        public int getStart() {
            return start;
        }

        public int getEnd() {
            return end;
        }
        
        // 수업 시작 시간을 기준으로 오름차순 정렬 || 수업 시작 시간이 같다면 종료 시간 기준
        @Override
        public int compareTo(Lecture o) {
            if(o.getStart()==getStart())
                return getEnd() - o.getEnd();

            return getStart() - o.getStart();
        }
    }

    public static int string_to_int(String string) {
        return Integer.parseInt(string);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = string_to_int(br.readLine());

        // 강의실 배정을 위한 수업 시작 시간과 종료 시간 저장
        List<Lecture> lectures = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = string_to_int(st.nextToken());
            int end = string_to_int(st.nextToken());

            lectures.add(new Lecture(start, end));
        }
        
        // 리스트 정렬
        Collections.sort(lectures);


        // 우선 순위 큐 생성 후 정렬한 리스트의 첫번째 값 저장
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(lectures.get(0).getEnd());

        // 리스트 값 검증하면서 필요한 강의실 개수 구하기
        for(int i = 1; i < N; i++) {
            // 현재 가장 빨리 끝나는 수업 시간이 들어올 데이터의 시작 시간보다 
            // 작거나 같으면 현재 가장 빨리 끝나는 수업 시간을 들어올 데이터의 
            // 끝나는 시간으로 갱신하기 위해 기존 값 삭제진행
            if(pq.peek() <= lectures.get(i).getStart()) 
                pq.poll();

            pq.add(lectures.get(i).getEnd());
        }

        // PQ의 남아있는 데이터의 개수가 필요한 강의실의 개수
        System.out.println(pq.size());
    }
}