백준 19598 - 최소 회의실 개수

문제

19598번: 최소 회의실 개수

---

조건

• 한 회의실에서 동시에 두 개 이상의 회의 불가능
• 1 ≤ N ≤ 10만
• 각 회의의 시작 시간과 끝나는 시간을 고려해서 최소 회의실 개수 출력

---

접근법

• 모든 회의를 저장할 공간과 진행 중인 회의들을 저장할 공간이 필요함.

  • meetings : 모든 회의를 저장하는 공간
    • meetings는 시작 시간을 기준으로 오름차순으로 정렬
    • ongoingMeetings에 시작 순서대로 차례대로 회의를 배정해야 되기 때문에
  • ongoingMeetings : 진행 중인 회의들을 저장하는 공간
    • ongoingMeetings는 끝나는 시간을 기준으로 오름차순으로 정렬

• meetings에서 회의를 하나씩 빼서 ongoingMeetings에 넣는다.

  

• 이때, 회의실을 새로 배정할 지 아니면 기존의 회의실에 넣을지 결정
• 5 10 회의는 회의실 새로 배정 → 진행중인 회의들의 끝나는 시간보다 시작 시간이 빠르기 때문에

  • 이때, 끝나는 시간을 기준으로 오름차순으로 정렬했기 때문에, 맨 위의 진행중인 회의(가장 빨리 끝나는 회의)만 보면 된다.

    

• 15 30 회의는 진행 중인 회의들 중 가장 빨리 끝나는 회의보다 시작 시간이 늦다.

  • 그러면 회의실을 새로 배정 안하고, 그 회의가 있는 공간을 대체해서 들어갈 수 있음.

    

• 이런 식으로 Meetings에 회의가 없을때까지 반복하고, 최종적으로 ongoingMeetings의 크기를 구하면 최소 회의실 개수를 얻을 수 있다.

---

문제 풀이

public class p19598 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        PriorityQueue<Meeting> meetings = new PriorityQueue<>(new Comparator<Meeting>() {
            @Override
            public int compare(Meeting m1, Meeting m2) {
                if (m1.start == m2.start) {
                    return m1.end - m2.end;
                }
                return m1.start - m2.start;
            }
        });

        PriorityQueue<Meeting> ongoingMeetings = new PriorityQueue<>(new Comparator<Meeting>() {
            @Override
            public int compare(Meeting m1, Meeting m2) {
                return m1.end - m2.end;
            }
        });

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

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings.add(new Meeting(start, end));
        }

        ongoingMeetings.add(meetings.poll());

        while (!meetings.isEmpty()) {
            Meeting nextMeeting = meetings.poll();

            if (ongoingMeetings.isEmpty()) {
                ongoingMeetings.add(nextMeeting);
            }

			//회의실 새로 배정
            else if (nextMeeting.start < ongoingMeetings.peek().end) {
                ongoingMeetings.add(nextMeeting);
            }
	
			//기존의 회의실에 회의 추가
            else if (nextMeeting.start >= ongoingMeetings.peek().end) {
                ongoingMeetings.poll();
                ongoingMeetings.add(nextMeeting);
            }

        }

        System.out.println(ongoingMeetings.size());

    }

    public static class Meeting {
        int start;
        int end;

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