[백준] 1374 강의실

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

 

풀이

구하고자 하는 것 : 필요한 최소 강의실 개수

 

해당 값을 구하기 위해 우선 시작 순서가 빠른 순서로 정렬

 

만약 시작 시간이 같다면 끝나는 시간이 더 빠른 걸로 정렬

 

no	시작 시간	종료 시간
3	2	14
1	3	8
5	6	20
8	6	27
2	7	13
4	12	18
6	15	21
7	20	25

 

강의실이 필요한 경우는

• 이전 강의 종료 시간 > 다음 강의 시작 시간

해당 경우에 강의실이 추가로 필요하다.

 

위 예제로 한번 천천히 보자

 

3번 강의(2 - 14)는 1번 강의실을 사용한다.

1번 강의(3 - 8)는 1번 강의실이 이미 사용중이므로 2번 강의실에서 진행

5번 강의(6 - 20) 또한 1,2번 강의실이 모두 강의 진행 중이므로 3번 강의실에서 진행

 

이런식으로 가다가 4번 강의(12 - 18)는 1번 강의를 진행했던 2번 강의실이 비어있으므로 해당 강의실에서 진행하면 된다.

 

즉 가장 빨리 끝나는 강의 시간대로 정렬을 유지한다면 어떤 강의실에서 강의를 이어 나갈 수 있는지 알 수 있음 

또한 해당 강의실을 이어서 사용하기 때문에 기존의 강의는 빼고 해당 강의의 끝나는 시간을 넣어야 됨

 

이를 위해 우선순위큐로 종료 시간을 가장 빨리 끝나는 시간 즉 오름차순 순으로 정렬 유지

 

 

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

public class Main {
    private static class Class{
        int start;
        int end;
        public Class(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));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        List<Class> classes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int no = stoi(st.nextToken());
            int s = stoi(st.nextToken());
            int e = stoi(st.nextToken());
            classes.add(new Class(s,e));
        }

        classes.sort((o1, o2) -> {
            if (o1.start == o2.start) {
                return o1.end - o2.end;
            }
            return o1.start - o2.start;
        });

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

        for (Class c : classes) {
        	//비어있다면 추가
            if (pq.isEmpty()) {
                pq.add(c.end);
                continue;
            }
            //시작 시긴 < 가장 빨리 끝나는 강의 시간
            //즉 가장 빨리 끝나는 강의보다 더 빨리 시작 하므로 어떤 강의실도 쓸 수 없으므로 추가
            if (c.start < pq.peek()) {
                pq.add(c.end);
            } else {
            	//강의 시작 시간과 종료 시간은 겹쳐도 무방하므로 >= 조건을 받을 수 있음
                //poll() 한다는 것 자체가 해당 강의실을 쓴다는 의미
                //따라서 poll() 후에 add()
                pq.poll();
                pq.add(c.end);
            }
        }

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

    private static int stoi(String v) {
        return Integer.parseInt(v);
    }

}

 

 

후기

그리디는 단순한데 어렵다.