백준_11000_강의실배정

https://www.acmicpc.net/problem/11000

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

public class Main {
    static int N;
    static class Lecture{
        int start, end;
        Lecture(int start, int end){
            this.start = start;
            this.end = end;
        }
    }

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

        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[i] = new Lecture(start,end);
        }

        Arrays.sort(list, (l1, l2) -> l1.start != l2.start ? l1.start - l2.start : l1.end - l2.end);

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.offer(list[0].end);

        for(int i = 1; i < N; i++){
            if(pq.peek() <= list[i].start){ // 안겹치는 경우
                pq.poll(); // 현재있는 강의실에 지금 배정할 수업도 배정할수 있는것!
            }
            pq.offer(list[i].end);
        }
        System.out.print(pq.size());
    }
}

1. 가장 일찍 시작하는 강의 순으로 정렬 , 시작 시간이 같다면 짧은 강의 먼저 앞으로 오도록 정렬

Arrays.sort(lectures, (l1, l2) -> l1.start == l2.start ? l1.end - l2.end : l1.start - l2.start);

👉 즉 배정 순서를 가장 빠른 강의부터 해준것

• 그래야 항상 배정된 강의의 시작 시각보다 빠른 배정이 안된 강의는 없음!
• 이미 배정된 강의의 끝시간과 배정할 강의의 시작 시간만 비교해주면 겹치는 지 안겹치는지 판단 가능하기 때문
• 이미 배정이 된 강의가 무조건 먼저 시작했음

2. 큐에서는 알아서 끝시간 이 가장 빠른 순으로 정렬된다.

가장 빠른(작은) 종료시간이 peek()에 오게됨

참고

https://steady-coding.tistory.com/253

https://velog.io/@jkh9615/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-11000-%EA%B0%95%EC%9D%98%EC%8B%A4-%EB%B0%B0%EC%A0%95-Java