[백준] 11000번 : 강의실 배정 – JAVA [자바]

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

 

---

문제

---

문제 풀이

문제 접근 방법:

1. 수업을 정렬하여 집행 순서 정하기

• 수업 시작 시간을 기준으로 오름차순 정렬한다.
• 같은 시작 시간이면 종료 시간을 기준으로 정렬한다

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

• 종료 시간이 가장 빠른 수업부터 관리하여 강의실을 재사용할 수 있는지 확인한다.
• 종료 시간이 가장 빠른 수업을 추적하기 위해 우선순위 큐(Priority Queue, Min-Heap) 를 사용한다

3. 그리디 알고리즘

• 현재 진행 중인 강의 중 가장 빨리 끝나는 강의와 새 강의의 시작 시간을 비교한다.
• 만약 현재 진행 중인 강의가 끝난 후 새 강의를 배정할 수 있다면, 기존 강의실을 재사용한다.
• 그렇지 않다면 새로운 강의실을 추가해야 한다.

4. 강의실 개수 계산

• 강의실 개수는 우선순위 큐에 저장된 수업 개수와 같다.

---

코드

import java.io.*;
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());
        Lecture[] arr = new Lecture[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            arr[i] = new Lecture(start, end);
        }
        Arrays.sort(arr, new Comparator<Lecture>() {
            @Override
            public int compare(Lecture o1, Lecture o2) {
                return o1.start - o2.start;
            }
        });
        PriorityQueue<Lecture> pq = new PriorityQueue<>();
        pq.add(arr[0]);
        for (int i = 1; i < n; i++) {
            Lecture current = pq.peek();
            if (current.end <= arr[i].start) {
                pq.poll();
                current.end = arr[i].end;
                pq.add(current);
            } else {
                pq.add(arr[i]);
            }

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

    }


    public static class Lecture implements Comparable<Lecture> {
        int start;
        int end;

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

        @Override
        public int compareTo(Lecture o) {
            if (this.end == o.end) return this.start - o.start;
            return this.end - o.end;
        }
    }

}

 

---

코드 설명

1. 입력 처리:

• BufferedReader를 사용하여 빠르게 입력을 받는다.
• Lecture 클래스를 사용하여 수업 시작 시간과 종료 시간을 저장한다.

2. 정렬:

• 수업 시작 시간을 기준으로 정렬한다.

3. 우선순위 큐 활용:

• 종료 시간이 가장 빠른 수업을 PriorityQueue로 관리한다.
• 현재 진행 중인 가장 빨리 끝나는 수업과 새로운 수업의 시작 시간을 비교하여 강의실을 재사용할 수 있는지 확인한다.

 

시간 복잡도

정렬: O (N log N)

우선순위 큐 연산: O (N log N)

총 시간 복잡도: O (N log N)