[백준][JAVA] BOJ 11000 강의실 배정

 

문제 읽기🤔

---

문제

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

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

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

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

 

입력

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

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

 

N이 최대 200,000이기 때문에 모든 경우의 수를 따진다면 O(n^2) -. 200,000^2으로 무조건 시간초과

 

출력

강의실의 개수를 출력하라.

 

예제 입력

3 
1 3 
2 4 
3 5

예제 출력

2

 

 

문제 풀이📝

---

https://gaebalsaebalpark.tistory.com/12

[백준][JAVA] BOJ 1931 회의실 배정

 

전에 포스팅한 회의실 배정과 매우 유사한 문제이다.

다만, 최대 회의 개수를 도출하는 것이 아닌, 모든 강의를 수행하기 위해 필요한 최소의 강의실 개수를 도출해내야 한다는 차이가 있다.

그러므로 회의실 배정을 풀 때는 끝나는 시간을 기준으로 정렬하였다면,

강의실 배정을 풀 때는 시작하는 시간이 빠른 순으로 정렬하여야 한다.

만약 시작하는 시간이 같다면 끝나는 시간이 빠른 순으로 정렬한다.

시간이 짧은 것끼리 연결해야 한 강의실을 최대로 사용할 수 있기 때문이다. (회의실 배정을 떠올려보자!)

 

이전 포스팅의 예제 입력을 예시로 들어서 설명하겠다.

끝나는 시간을 기준으로 정렬한 경우 (회의실 배정)

시작하는 시간을 기준으로 정렬한 경우 (강의실 배정)

시작하는 시간을 기준으로 정렬하는 경우, 처음부터 순회하며 몇 개의 강의실을 생성해야 하는 지 알아낼 수 있다.

강의실에 배정된 모든 가장 마지막 강의들의 끝나는 시간이 현재 강의의 시작 시간보다 크다면 현재 강의는 새로운 강의실을 배정받아야 한다.

그렇지 않다면, 기존의 강의실에 연결할 수 있는 상태이므로,

현재 강의는 강의실에 있는 가장 마지막 강의들 중 적합한 강의의 뒤로 연결되게 된다.

그러나 모든 경우의 수를 따져가면서 위와 같은 타임 테이블을 순회한다면, 시간초과가 날 수 밖에 없다.

(N은 최대 200,000)

 

PriorityQueue<Long> timetables = new PriorityQueue<>();
timetables.offer(lectures.poll().end);	// lectures: 우선순위에 따라 정렬된 강의들
while(!lectures.isEmpty()) {
	// 회의실에 배정된 강의 중, 가장 끝나는 시간이 빠른 강의의 *끝나는 시간*
	Long end = timetables.peek();
	// 회의실에 배정되기를 기다리는 시작 시간이 가장 빠른 강의
	Lecture cur = lectures.poll();
	// 한 강의실에 두 강의를 배정할 수 있는 상태라면
	if (end <= cur.start){
		// 해당 강의실에 배정된 마지막 강의의 끝나는 시간을
		timetables.poll();
		// 새로운 강의의 끝나는 시간으로 갱신
		timetables.offer(cur.end); 
		continue;
	}
	//한 강의실에 배정할 수 없는 상태라면, 새로운 강의실 배정
	timetables.offer(cur.end); 
}

나는 timetables라는 우선순위 큐를 하나 선언하여 강의실에 배정된 마지막 강의의 끝나는 시간을 저장하고자 했다.

즉, timetables에 남아있는 요소들은 강의실 하나를 의미하게 된다.

 

먼저 회의실에 배정된 강의 중, 끝나는 시간이 가장 빠른 강의의 끝나는 시간과

회의실에 배정되기를 기다리는 강의 중, 시작하는 시간이 가장 빠른 강의의 시작하는 시간을 비교한다.

 

끝나는 시간이 시작하는 시간보다 크다면

두 강의는 한 강의실에 배정할 수 없는 상태이기 때문에 배정 대기 중인 강의는 새로운 강의실을 배정받아야 한다.

끝나는 시간이 시작하는 시간보다 작다면

두 강의는 한 강의실에 배정할 수 있으므로 가장 마지막 강의의 끝나는 시간을 새로운 강의의 끝나는 시간으로 갱신한다.

 

모든 강의들을 한 번씩 순회했다면, timetables에는 강의실의 개수 만큼의 원소들이 남아있게 된다.

 

 

구현🛠️

---

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

public class Main_11000 {

    static class Lecture implements Comparable {

        public long start;
        public long end;

        public Lecture(long start, long end){
            this.start = start;
            this.end = end;
        }


        @Override
        public int compareTo(Object o) {
            Lecture other = (Lecture)o;
            if (this.start < other.start){
                return -1;
            }
            else if(this.start == other.start){
                return Long.compare(this.end, other.end);
            }
            else
                return 1;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        PriorityQueue<Lecture> lectures = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long start = Long.parseLong(st.nextToken());
            long end = Long.parseLong(st.nextToken());
            lectures.offer(new Lecture(start, end));
        }

        PriorityQueue<Long> timetables = new PriorityQueue<>();
        timetables.offer(lectures.poll().end);
        while(!lectures.isEmpty()) {
            // 회의실에 배정된 강의 중, 가장 끝나는 시간이 빠른 강의의 *끝나는 시간*
            Long end = timetables.peek();
            // 회의실에 배정되기를 기다리는 시작 시간이 가장 빠른 강의
            Lecture cur = lectures.poll();
            // 한 강의실에 두 강의를 배정할 수 있는 상태라면
            if (end <= cur.start){
                timetables.poll();  // 이전 강의의 끝나는 시간을
                timetables.offer(cur.end);  // 새로운 강의의 끝나는 시간으로 갱신
                continue;
            }
            //한 강의실에 배정할 수 없는 상태라면, 새로운 강의실 배정
            timetables.offer(cur.end);
        }

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

 

 

실행결과✅

---