백준 11000번: 강의실 배정

문제 풀이

1. 강의 일정을 시작 시간 기준으로 정렬
2. 우선순위 큐(Priority Queue)를 사용하여 강의실을 관리
   • 가장 먼저 끝나는 강의의 종료 시간을 기준으로 새로운 강의를 배정할 수 있는지 확인
   • 현재 진행 중인 강의 중 가장 빨리 끝나는 시간보다 새로운 강의의 시작 시간이 크거나 같으면 기존 강의실 사용 가능
   • 그렇지 않으면 새로운 강의실 추가

 

코드 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] lectures = new int[N][2];
        
        for (int i = 0; i < N; i++) {
            lectures[i][0] = sc.nextInt(); // 시작 시간
            lectures[i][1] = sc.nextInt(); // 종료 시간
        }
        sc.close();
        
        // 시작 시간을 기준으로 정렬
        Arrays.sort(lectures, Comparator.comparingInt(o -> o[0]));
        
        // 종료 시간을 저장할 우선순위 큐 (최소 힙)
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(lectures[0][1]); // 첫 번째 강의 종료 시간 추가
        
        for (int i = 1; i < N; i++) {
            if (pq.peek() <= lectures[i][0]) {
                pq.poll(); // 기존 강의실 재사용 가능
            }
            pq.add(lectures[i][1]); // 새로운 강의 종료 시간 추가
        }
        
        // 우선순위 큐에 남아 있는 요소 개수가 필요한 강의실 수
        System.out.println(pq.size());
    }
}

 

코드 설명

1. 강의 정렬

• 강의 시작 시간을 기준으로 오름차순 정렬합니다.

2. 우선순위 큐를 이용한 강의실 배정

• 가장 먼저 끝나는 강의(종료 시간 기준)를 우선적으로 확인하기 위해 최소 힙(PriorityQueue)을 사용합니다.
• 현재 강의의 시작 시간이 가장 빨리 끝나는 강의의 종료 시간보다 크거나 같다면 기존 강의실을 사용할 수 있습니다.
• 그렇지 않다면 새로운 강의실이 필요하므로 종료 시간을 추가합니다.

3. 결과 출력

• 최종적으로 pq에 남아 있는 종료 시간 개수가 필요한 강의실 수입니다.

 

시간 복잡도

• 정렬: O(N log N)
• 우선순위 큐 연산: O(N log N)
• 총 시간 복잡도: O(N log N)