[코딩테스트] 회의실 배정 (그리디 알고리즘)

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.
각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

입력

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데
이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.
회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

예시 입력 1

5
1 4
2 3
3 5
4 6
5 7

예시 출력 1

3

생각

• 회의실 하나를 최대한 많은 회의에서 사용해야 한다 -> 회의가 최대한 빨리 끝나야 한다라고 생각하여 종료 시간 기준으로 회의들을 정렬하였다
  • 또한 회의 종료 시간이 같을 경우를 대비해서 종료 시간이 같을 경우, 시작 시간을 기준으로 정렬하였다
• 회의 시간을 반복문을 돌면서, 이번 index의 회의의 시작 시간이, 이전 회의의 종료시간보다 늦거나 동일하면, 그 회의를 Count 하였다

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class AssignMeetingRoom {

    static class Meeting implements Comparable<Meeting> {

        private int start;
        private int end;

        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;
            else
                return this.end - o.end;
        }
    }

    public int getMeetingCnt(int n, List<Meeting> info) {

        Collections.sort(info);
        int cnt = 1;
        int lastEndTime = info.get(0).end;

        for (int i = 1; i < n; i++) {
            if (info.get(i).start >= lastEndTime) {
                cnt++;
                lastEndTime = info.get(i).end;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        AssignMeetingRoom T = new AssignMeetingRoom();
        Scanner kb = new Scanner(System.in);

        List<Meeting> info = new ArrayList<>();

        int n = kb.nextInt();
        for (int i = 0; i < n; i++) {
            info.add(new Meeting(kb.nextInt(), kb.nextInt()));
        }

        System.out.println(T.getMeetingCnt(n, info));
        kb.close();
    }

}

정리

그리디 알고리즘

• 매 순간 최적의 선택을 하여, 전체적인 해답을 찾아가는 방법
• 매 선택에서 지금 이 순간 가장 좋은 것만 고르는 것

• 그리디 알고리즘은 문제를 푸는 것은 간단하지만, 기준을 선택하는 것이 어려운 것 같다. 매 순간 최적의 선택이, 전체적으로 최적의 선택이 되도록 기준을 잘 정하는 연습이 필요해 보인다! 😀😀

문제 출처