[Algorithm]백준_1931 회의실배정 JAVA

문제

한 개의 회의실과 N개의 회의(시작 시간, 끝 시간)가 주어졌을때, 각 회의가 겹치지않게 사용할 수 있는 최대 회의 수를 구하는 문제입니다.

풀이 방식

처음에 이중 for문을 순회하면서 다음 회의의 시작시간이 현재 회의의 끝 시간과 같거나 큰 경우만 count 해준 후, 마지막에 가장 큰 count값을 리턴했더니 시간초과로 실패했습니다. 😷
그래서 그리디 알고리즘을 적용해서 푸니 통과했습니다.

회의 객체를 만들고, Comparable<>을 implements 받아 회의 끝 시간으로 작은 순으로 (끝 시간이 같으면 회의 시작 시간이 작은 순으로) 정렬합니다.

소스 코드

static int N;

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

        ArrayList<Meeting> meetings = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            StringTokenizer st = new StringTokenizer(input);

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            meetings.add(new Meeting(start, end));
        }

        Collections.sort(meetings);

        int end =0;
        int count =0;
        for(Meeting m : meetings) {
            if (end <= m.start) {
                count++;
                end = m.end;
            }
        }
        System.out.println(count);
    }

    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 1;
            } else if (this.end == o.end) {
                if(this.start > o.start) {
                    return 1;
                } else {
                    return -1;
                }
            } else {
                return -1;
            }
        }
    }

후기

그리디 알고리즘으로 푸는 걸 알았으면서도 모든 경우를 체크해서 풀었습니다.
이런 습관을 좀 버려야될텐데