[백준] 11000 : 강의실 배정 (Priority Queue 이용하기) - JAVA

백준 알고리즘 분류 (그리디 알고리즘)

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

11000번: 강의실 배정

 

 

# 문제

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

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

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

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

 

# 예제

입력 : 

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 10^9)

3
1 3
2 4
3 5

 

출력 

2

 

# 필요개념

강의실의 개수를 최소화 해야 하므로, 낭비되는 시간을 최소화해야한다. 처음에 시간복잡도 때문에 애를 먹었는데, n이 20만이므로 O(n^2) 가 나오는 알고리즘은 시간초과가 발생할 수 있다. 이중 반복문을 사용하면 시간초과가 나올 확률이 높다는 의미이다.

 

우선 예제를 기준으로 하면 아래와 같이 나타낼 수 있다.

같은 강의실을 이용하려면 앞 수업의 끝나는 시간 <= 뒤 수업의 시작 시간 을 만족시켜야 한다. 그래서 끝나는 시간을 기준으로 오름차순을 만들어주는 우선순위 큐를 사용하였다. 이 안에 수업의 교실당 수업의 끝나는 시간을 넣어둔다.

 

나는 두가지 저장공간을 사용하였다.

• 리스트 : 처음에 입력을 받을 때 리스트에 저장한다. 난 별도의 객체를 사용하여 수업의 시작시간을 기준으로 오름차순 정렬을 하고, 시작시간이 같을 경우 끝나는 시간을 기준으로 오름차순 정렬을 했다.
• 우선순위 큐 : 각 "강의실 별" 끝나는 시간을 넣어두었다. 위 예제로 가정하면 우선순위 큐에는 4,5가 들어간다.

 

우선순위 큐의 peek()은 끝나는 시간 중 가장 일찍 끝나는 시간이 들어갈 것이고, 시작시간과 비교했을 때 이보다 작다면 해당 수업의 끝나는 시간을 우선순위 큐에 넣는 식이다. 

 

리스트를 사용하기 위해 Lect 객체를 생성해 사용했다! 이 문제에서 크게 중요하진 않지만 배열을 sort할 때 걸리는 시간(O(n)) 보다 리스트를 sort할 때 걸리는 시간 (O(1))이 작기 때문이다.

# Code

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Lect> lst = new ArrayList<>();
        for (int i = 0 ; i < n ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            Lect l = new Lect(s,e);
            lst.add(l);
        }
        Collections.sort(lst, new Comparator<Lect>() {
            @Override
            public int compare(Lect o1, Lect o2) {
                if (o1.start != o2.start) return o1.start - o2.start;
                return o1.end - o2.end;
            }
        });
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(lst.get(0).end);
        for (int i = 1 ; i < n ; i++) {
            if (queue.peek() <= lst.get(i).start) queue.poll();
            queue.add(lst.get(i).end);
        }
        System.out.println(queue.size());
    }
}
class Lect {
    int start;
    int end;
    public Lect(int s, int e) {
        this.start = s;
        this.end = e;
    }
}

 

# 결과