[백준] 19598번 최소 회의실 개수 (JAVA)

문제

- N개의 회의를 모두 진행할 수 있는 최소 회의실 개수 구하기

- 각 회의는 시작 시간과 끝나는 시간이 주어짐

- 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없음

- 회의는 한 번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있음

- 회의의 시작 시간은 끝나는 시간보다 항상 작음

 

해결방법

회의 시작시간이 순서없이 입력되고 있기 때문에 회의 시간을 입력 받을 때, 시작 시간을 기준으로 정렬을 해주었다. 시작 시간을 기준으로 정렬을 하고 회의실을 하나씩 배정하면서 끝나는 시간을 기록해두었고, 끝나는 시간보다 시작 시간이 큰 회의가 있다면 해당 회의실에 다음 회의로 일정을 잡으면 되기 때문에 haveMeetingRoom 변수로 들어갈 수 있는 회의실의 유무를 판단하여 코드를 짰다.

 

코드

import java.io.*;
import java.util.*;

// 회의 시간 클래스
class Time implements Comparable<Time>{
    int start;
    int end;

    public Time(int start, int end) {
        this.start = start;
        this.end = end;
    }
	
    // 시작 시간 순 정렬 (시작 시간이 같다면 끝나는 시간이 빠른 것부터 정렬)
    @Override
    public int compareTo(Time o) {
        if(this.start == o.start) return this.end - o.end;
        else return this.start - o.start;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Time> meetings = new ArrayList<>();		// 회의 시간
        List<Integer> nowMeetings = new ArrayList<>();		// 현재 진행 중인 회의 정보

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

	// 시작 시간 순 회의 정렬
        Collections.sort(meetings);
		
        // 첫번째 회의
        int result = 1;
        nowMeetings.add(meetings.get(0).end);		// 현재 진행 중인 회의 정보 리스트에 끝나는 시간 입력
		
        // 다음 회의부터 회의실 배정
        for(int i = 1; i<N; i++){
            int start = meetings.get(i).start;
            int end = meetings.get(i).end;
            boolean haveMeetingRoom = false;
            // 현재 진행 중인 회의 정보 리스트 탐색
            for(int j = 0; j<nowMeetings.size(); j++){
            	// 다음 진행시켜야할 회의가 진행 중인 회의 정보 리스트가 끝나는 시간보다 큰 회의가 있다면
                if(start >= nowMeetings.get(j)){
                    // 그 회의실에 다음 회의 끝나는 시간 넣어주기
                    haveMeetingRoom = true;
                    nowMeetings.remove(j);
                    nowMeetings.add(end);
                    break;
                }
            }
            // 만약 들어갈 수 있는 회의실이 없다면
            if(!haveMeetingRoom) {
            	// 새로운 회의실 배정 필요
                result++;
                nowMeetings.add(end);
            }
        }
	// 최종 회의실 개수 출력
        System.out.println(result);
    }
}