백준 19598 "최소 회의실 개수" (JAVA)

🔍 문제링크

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

문제 요약

• N개의 회의가 주어질 때, 동시에 두 개 이상의 회의를 진행할 수 없음.
• 단, 회의가 끝나는 동시에 다음 회의가 시작 가능.
• 모든 회의를 진행하는 데 필요한 최소 회의실 개수를 구함

---

🛠 풀이 및 알고리즘

1. 회의를 시작 시간 기준으로 정렬
   • 회의가 일찍 시작하는 순서대로 배정하기 위해 정렬.
   • 같은 시작 시간이라면, 종료 시간 기준 정렬이 필요할 수도 있음.
2. 우선순위 큐(PriorityQueue) 활용
   • 현재 진행 중인 회의들의 종료 시간을 저장하여 관리.
   • 새로운 회의를 시작할 때 가장 빨리 끝나는 회의보다 늦게 시작하면 기존 회의실을 재사용.
3. 우선순위 큐의 크기가 곧 필요한 최소 회의실 개수
   • 진행 중인 회의의 종료 시간이 새로운 회의의 시작 시간보다 작거나 같다면 회의실을 반환(poll()).
   • 그렇지 않다면 새로운 회의실이 필요하므로 종료 시간을 추가(add()).

---

💡 코드

public class Baekjoon_19598 {

    static class Meeting{
        int start,end;
        Meeting(int start,int end){
            this.start=start;
            this.end=end;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Meeting> meetings = new ArrayList<>();
        for(int i =0 ;i<n;i++){
            meetings.add(new Meeting(sc.nextInt(),sc.nextInt()));
        }

        // 회의 시작순으로 정렬
        meetings.sort((a,b)-> a.start - b.start);

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(Meeting meeting : meetings){
            pq.add(meeting.end);
            
            if(pq.peek() <= meeting.start){
                pq.poll();
            }
        }
        System.out.println(pq.size());
    }
}

---

🏆 시간 복잡도 분석

• 회의 정렬: O(N log N)
• 우선순위 큐 관리: O(N log N)
• 총 시간 복잡도: O(N log N)