[백준] 1931. 회의실 배정

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

1931번: 회의실 배정

이번 문제는 그리디 문제로, 회의 종료 시간이 빠른 순서대로 정렬한 뒤 차례대로 회의를 진행하면 된다.

 

그런데 주의할 점은, 만약 회의 종료 시간이 같다면 회의 시작 시간이 빠른 순으로 정렬해야 한다. 예를 들어, 다음과 같이 회의가 있다고 가정하자.

1 ~ 3
4 ~ 8
8 ~ 8

 

만약 회의 시작 시간이 빠른 순으로 정렬하는 것을 고려하지 않고 다음 순서로 진행한다면, 

1 ~ 3
8 ~ 8
4 ~ 8

 

8 ~ 8 회의를 진행한 후 preMeetingEndTime 변수의 값은 8이 되어 4 ~8 회의를 진행할 수 없다. 그러나 회의 시작 시간이 빠른 순으로 정렬한다면, 4 ~ 8 회의를 먼저 진행한 후 preMeetingEndTime 변수의 값이 8이 되고 8 ~8 회의도 진행할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;

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

public class Main {

    static int n;
    static List<Meeting> meetingList = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        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());
            meetingList.add(new Meeting(start, end));
        }

        Collections.sort(meetingList);

        int answer = 0;
        int preMeetingEndTime = 0;
        for (int i = 0; i < meetingList.size(); i++) {
            Meeting meeting = meetingList.get(i);
            if (meeting.start >= preMeetingEndTime) {
                answer++;
                preMeetingEndTime = meeting.end;
            }
        }

        System.out.println(answer);
    }

    static class Meeting implements Comparable<Meeting> {
        int start;
        int end;

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

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

기발하게 그리디 알고리즘을 사용하는 해결법을 떠올리는 것이 아직 익숙하지 않다..! 그리고 문제에 "회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다."라는 설명이 있는데, 이런 부분을 특히 주의하여 반례를 잘 생각해야겠다.