백준 11000(JAVA)

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

즉, 최소의 강의실을 배정할수 있도록 하라는 문제이다.
입력은 강의실의 개수가 입력되고 그다음부터 각 강의의 시작시간과 끝시간이 입력된다.

풀이

입력되는 강의실의 개수가 최대 200,000개이다.
완전탐색으로는 시간초과가 날게 뻔하다.

일단 시작시간을 기준으로 오름차순 정렬해야한다. 시작시간이 같다면 끝나는 시간을 기준으로 오름차순 정렬한다.
왜 정렬하냐면 최소의 강의실을 배정하기 위해서는 시간을 가장 효율적으로 써서 배정해야한다. 즉 버리는 시간을 최소한으로 해야한다.
시작시간을 기준으로 정렬한다면 종료시간만 생각하며 강의실을 배정할수 있다.
시작시간을 기준으로 정렬하지 않는다면 시작시간도 고려하면서 강의실을 배정해야한다.
종료시간도 그러하다.
즉, 시작시간을 기준으로 정렬하는 것은 최소의 강의실을 배정하기 위해 준비해야하는 조건이다.

그리고 우선순위큐를 이용한다.
우선순위큐는 내부적으로 힙이 구현되어있어 탐색에 굉장히 빠르다.
그렇기에 현재 우선순위가 가장 높은 녀석을 찾는데 굉장히 빠르므로 우선순위가 가장높은 녀석은 종료시간이 가장 작은 녀석으로 하자.

1 3
1 4
3 5
4 6

총 네개의 수업이 있다.
(시작시간 기준으로 정렬한상태임, 같으면 종료시간 기준으로 정렬)

1. 우선순위큐에 1 3 수업의 종료시간을 넣는다. 우선순위큐 : (3)
2. 1 4 수업의 시작시간과 우선순위큐의 가장 작은 종료시간을 비교한다. 종료시간이 더 크기 때문에 같은 강의실을 배정할수없다. 그래서 우선순위큐에 1 4 의 종료시간을 넣는다. (3, 4), 이 과정은 시작시간을 기준으로 정렬이 되어있기에 가능한것이다. 시작시간을 기준으로 정렬이 되어있지 않은 상태라면 강의실을 새로 배정해야한다는 사실을 확신할수없다.
3. 3 5 수업의 시작시간과 우선순위큐의 가장 우선순위가 높은 종료시간 3을 비교한다. 강의실을 새롭게 배정할 필요가 없다. 우선순위큐에서 poll을 하고 새로운 종료시간 5를 offer한다. 우선순위큐 : (4, 5)
4. 4 6수업의 시작시간 4와 우선순위큐 4와 비교한다. 새롭게 강의실 배정할 필요가 없다. poll하고 종료시간 6을 offer한다. 우선순위큐 : (5, 6)

배정한 강의실의 개수는 우선순위큐의 size이다.

코드

package baekjoon.그리디;

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

class Lesson {
    int start;
    int end;

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

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }

    @Override
    public String toString() {
        return "Lesson{" +
                "start=" + start +
                ", end=" + end +
                '}';
    }
}

public class Main11000 {
    static int N;
    static List<Lesson> list = new ArrayList<>();

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

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            list.add(new Lesson(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        Collections.sort(list, Comparator.comparingInt(Lesson::getStart).thenComparing(Lesson::getEnd));
        //시작시간 정렬 -> 끝나는 시간 정렬,

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(list.get(0).getEnd());
        for(int i = 1; i < N; i++){
            if(pq.peek() <= list.get(i).getStart()){
                pq.poll();
                pq.offer(list.get(i).getEnd());
            }else{
                pq.offer(list.get(i).getEnd());
            }
        }

        System.out.println(pq.size());
    }

}

/**
 최소의 강의실을 배정해야되는 문제

 풀이
 수업을 안하는 버리는 시간을 줄이기 위해 시작시간을 기준으로 정렬, 시작시간 같으면 종료시간을 기준으로 정렬함
 이 정렬은 수업을 최대한 버리지 않도록 함
 시작시간이 그럼 작은것부터 정렬이 되기 때문에 종료시간만 생각하며 강의실을 배정할수 있음
 정렬하지않으면 시작시간도 고려를 해야함

 그리고 우선순위큐 (정수 오름차순 정렬 기준)를 이용
 우선순위큐는 끝나는 시간만 알고있음

 1 3
 1 4
 3 5
 4 6

 네개의 수업(정렬된상태)

 일단 먼저 우선순위큐에 1 3 수업의 끝나는 시간 3을 넣는다
 그다음 수업 1 4 에 대해서 우선순위 큐 가장위에있는 3(우선순위 큐 가장위에있는 녀석이 종료를 가장 빨리 하는 녀석이다.)
 과 시작시간 1을 비교한다. 시작시간으로 정렬한 상태이므로 강의실을 새롭게 배정해야한다는 확신을 할수있음
 그래서 우선순위큐에 1 4 의 끝나는 시간 4를 넣는다. 그럼 우선순위큐는 [3, 4] 의 데이터가 존재한다.
 그다음 수업 3 5 에 대해서 시작시간 3과 우선순위큐 맨위에있는 3을 비교하면 3 >= 3이므로 우선순위큐의 3을 pop하고
 새로운 종료시간 5를 넣는다. 그럼 우선순위큐는 [4, 5]이다.
 그리고 4 6 수업에 대해서 4와 우선순위큐 맨위의 4를 비교하면 4>= 4 이므로 pop하고 offer하면 [5, 6]이되고
 배정된 강의실의 개수는 pq의 size이다.

 우선순위큐는 내부적으로 heap이 구현되어있다. 그래서 우선순위에 따라 힙의 구조를 바꾸는데 굉장히 빠르다.
 애초에 입력되는 수업의 개수가 200,000 개이므로 완전탐색은 무조건 시간초과이므로 내부적으로 힙이 구현되어있는
 우선순위큐를 이용함.

 암튼 어려운문제다. 생각하기에
 **/

너무 어려워서 참고를 많이했다. 왜 시작시간 기준으로 정렬하는 것이 필요한지 이해하는데 많은 시간이 걸렸다.