[ 백준/Java ] 1931. 회의실 배정

백준 링크 : https://www.acmicpc.net/problem/1931

 

🌱 [ 문제 요약 ]

한개의 회의실과 N개의 회의가 있다.

각 회의 시작시간과 끝나는 시간이 주어 질때 회의실에서 할 수 있는 최대 회의 개수를 구하라.

( 단. 회의는 중단이 불가능 하며, 회의가 끝나는 동시에 다음 회의가 시작 될 수 있다. )

( 회의 시작 시간과 끝나는 시간이 같을 수 있다. 시작하자마자 끝난 것이다. )

 

🌱 [ 문제 풀이 ]

어떻게 접근 해야 할지 어렵다.

예시를 통해 알아보자.

 

1번 예시

 

2

1 3

2 2

 

회의 시간이 짧은 2시 ~ 2시 회의를 먼저 배정 하는게 어떨까?

 

2번 예시

 

3

1 3

2 4

3 5

 

회의 시간이 모두 같은데...

회의 시간 순서로 정렬 하게 된다면 어떻게 배정 해야 할지 모르겠다.

 

3번 예시

 

2

1 3

2 3

 

두 회의 모두 3시에 끝난다.

두 회의 모두 먼저 배정 해도 된다.

회의 끝나는 시간 순서로 정렬 하면 어떨까?

위 예시를 통해 회의 끝나는 시간 순서로 정렬 하였다.

 

정렬 후 회의 시작 시간을 통해 다음 회의 진행 여부를 알 수 있다.

예를 들면 4시에 회의가 끝났다면 다음 회의는 시작시간은 4시 부터 이다.

---

🔥  [ 주의 : 정렬 기준 ]

예시

 

2

3 3

1 3

 

ans : 2

wrong aws : 1

 

회의 끝나는 시간이 같다면 회의 시작 시간순으로 정렬 해야 한다.

---

[ 전체 코드 ]

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int meetingCount = Integer.parseInt(br.readLine());

        // 입력
        List<Meeting> meetings = new ArrayList<>();
        for(int i = 0; i < meetingCount; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings.add(new Meeting(start,end));
        }

        // 정렬
        meetings.sort((Meeting meeting1,Meeting meeting2) -> {
            int endResult = meeting1.end - meeting2.end;
            if(endResult != 0) return endResult;
            return meeting1.start - meeting2.start;
        });

        // 강의실 최대 이용 수
        Queue<Meeting> queue = new LinkedList<>(meetings);
        int count = 0;
        int endTime = 0;
        while(!queue.isEmpty()){
            Meeting curMeeting = queue.poll();
            if(curMeeting.start >= endTime){
                count++;
                endTime = curMeeting.end;
            }
        }
        System.out.print(count);
    }

    static class Meeting{
        private int start;
        private int end;

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