[java] 11000 강의실 배정

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

주어진 백준 예시를 보면서 이해해보자면
1 시작 3 끝
2 시작 4 끝
3 시작 5 끝 이므로,

강의실 1 : 1 시작 3 끝, 3 시작 5 끝
강의실 2 : 2 시작 4 끝
이렇게 2개의 강의실만 사용하면 됩니다.

따라서 들어온 수업시간표를 시작 시간 순으로 정렬하여,
반복문을 돌리며 순서대로 시작시간과 이전 끝나는 시간을 비교하면 됩니다.

정렬된 배열[i]의 시작 시간 과 이전에 시작된 강의가 끝나는 시간을 비교하면 되죠!
정렬된 배열[i] 는, 배열을 정렬해두고 반복문을 돌리면 되고
이전 끝나는 시간은 큐에 넣어 비교해줍니다.

그럼 제일 먼저 큐에 비교할 대상이 필요하므로, 첫번째로 시작하는 수업의 끝나는 시간을 큐에 넣어줘야 합니다.
여기서 시작 시간이 같으면서 끝나는 시간이 다를 수 있으므로, 시작시간이 같을 때 끝나는 시간이 짧은 순으로 정렬해줍니다.

또 위의 예시로 보자면

1. 시작 시간 순으로 정렬
1 3 , 2 4, 3 5

2. 첫번째로 시작하는 수업의 끝나는 시간을 큐에 넣음
1,3 이므로 Q = {3}

3. 반복문을 돌리며 정렬된 배열들을 돌면서 큐와 비교합니다.
그럼 2 4, 3 5 순으로 비교하겠죠

3-1. 2 4
시작 시간을 비교했을 때 2 < 3 이므로
이는 첫번째 강의가 끝나기 전에 두번째 강의가 시작한다는 의미로 강의실을 추가로 더 사용해야합니다.
따라서 끝나는 시간을 큐에 넣어줍니다.
Q = {4,3}

여기서 끝나는 시간이 짧은 순대로 정렬해야하므로 우선순위 큐를 사용해주어야 합니다.
Q = {3,4}

3-2. 3 5
우선순위 큐 이므로, 큐의 제일 앞에 있는 값을 가져와 비교합니다. Q = {3,4} 이므로 3
강의가 시작하는 시간과 비교합니다 . 3 == 3 이므로 이어서 강의실을 사용할 수 있습니다.
따라서 현재 Q 의 첫번째 값을 제거하고, 현재 강의가 끝나는 시간을 큐에 넣어줍니다.
Q = {4,5}

그래서 반복문이 끝났을 때 Q의 사이즈가 사용해야 할 강의실의 개수가 됩니다.

3. 코드

import java.util.*;
import java.io.*;
 
//  Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게
// Ti == Sj 인 경우 같은 강의실

// 시간 제한 1초 (1 ≤ N ≤ 200,000),  (0 ≤ Si < Ti ≤ 109)

class Time implements Comparable<Time>{ 
    int start, end;
    Time(int start, int end){
        this.start = start;
        this.end = end;
    }

    @Override
	public int compareTo(Time o) {
        if(this.start == o.start){ // 시작시간이 같으면 끝나는 시간이 낮은 순으로
            return this.end - o.end ;
        }else return this.start - o.start; // 시작시간 낮은 순대로 정렬
    }
}

class Main {
    static int N; // 수업 개수
    static Time[] arr ; 

    public static int stoi(String s){
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws Exception {
        // 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = stoi(br.readLine()); 
        arr = new Time[N];

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = (new Time(stoi(st.nextToken()), stoi(st.nextToken())));
        }

        Arrays.sort(arr); // 시작시간 순대로 정렬

        System.out.println(CountLectureRoom());

     }

     // 사용가능한 강의실 수를 세는 메소드
     public static int CountLectureRoom(){
        PriorityQueue<Integer> q = new PriorityQueue(); // 강의가 끝나는 시간을 저장
        q.add(arr[0].end); // 제일 첫번째 강의 끝나는 시간을 넣어줌

        for(int i=1;i<N;i++){
            System.out.println(q.toString());
            if(arr[i].start >= q.peek()){ 
                q.poll();
            }
            q.add(arr[i].end);
        }
        return q.size();
     }
}

---

이문제 너무 재밌게 풀었다 !! 재밌어 ~~