[백준 1931 : JAVA] 회의실 배정 / 그리디

문제

---

한 개의 회의실이 있는데, 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 [시작시간, 종료시간] 이 주어지고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 갯수를 구하라. 단, 회의는 한 번 시작하면 중단할 수 없고, 회의가 끝남과 동시에 다음 회의를 시작할 수 있다.

 

 

입력

---

첫째 줄에 회의의 수 N($1<=N<=100,000$)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 회의의 [시작시간, 종료시간] 정보가 공백으로 주어진다. 시작시간과 종료시간은 $2^{31}-1$보다 작거나 같은 자연수 또는 0이다.

 

 

출력

---

첫째 줄에 최대 사용할 수 있는 회의의 갯수를 출력한다.

 

 

 

풀이

---

해당 문제는 아주 유명한 Activity Selection Problem을 다루고 있습니다.

 

다음과 같은 상황을 가정해보겠습니다.

당신은 지금 놀이공원에 왔습니다. 여러가지 놀이기구를 탈 수 있는 활동(Activity)들이 있는데, 각 활동(Activity)들은 시작시간과 종료시간이 제각각입니다. 당신은 오랜만에 놀이공원에 왔기 때문에 최대한 많은 활동(Activity)들을 즐기고 돌아가고 싶습니다. 이때, 각각의 활동(Activity)들의 [시작시간, 종료시간]을 가지고 최대 몇 개의 활동(Activity)을 할 수 있는지 어떻게 찾을 수 있을까요?

 

입력(Input): 각 활동(Activity)들의 [시작시간, 종료시간]

선행조건: 종료시간을 기준으로 오름차순 정렬

[그림 1] 종료시간을 기준으로 오름차순 정렬된 활동(Activity) 목록

 

위 문제는 그리디 알고리즘을 이용해 아주 빠르고 효율적으로 결과를 도출해낼 수 있습니다.

위 활동(Activity) 목록을 보면 (1, 4)-(5, 7)-(8, 11)-(12, 14) 로 최대 4가지의 활동(Activity)을 즐길 수 있는 걸 알 수 있습니다. 그런데, 4가지 활동을 할 수 있는 조합은 이거 하나만 있는게 아닙니다. (3, 5)-(5, 7)-(8, 12)-(12, 14) 도 있고, 또 다른 조합도 있습니다.

 

여러 최적의 경우가 있지만, 그리디 알고리즘의 특성상 최적의 경우 한 가지만을 찾아낼 수 있습니다.

위 문제에 그리디 알고리즘을 적용하면 다음과 같습니다.

1. 종료시간이 가장 빠른 활동(Activity)을 선택합니다.
2. 다음 활동을 순차적으로 탐색하면서 앞에서 선택된 활동의 종료시간보다 큰 시작시간을 가지는 활동을 선택합니다.
3. 위 과정을 반복합니다.

 

위 알고리즘의 증명

만약 위와 같은 과정으로 구한 최적해에서의 첫 번째 활동인 (1, 4)를 포함하지 않는 최적해가 있다고 생각해봅시다. 그 최적해에서의 첫 번째 활동은 최소한 4초 이후에 끝나는 활동일 것입니다. 그렇다는건 이 활동은 (1, 4)로 대체해도 항상 성립함을 의미합니다 !

 

위 표에서 또 다른 최적해는 (3, 5)-(5, 7)-(8, 12)-(12, 14) 가 있는데 (3, 5)는 항상 (1, 4)로 대체할 수 있습니다 !

5라는 종료시간을 가지는 활동1을 선택해도 겹치지 않는 활동2를 선택할 수 있었는데, 그보다 빠른 종료시간을 가지는 활동으로 대체가 안될리가 없기 때문입니다.

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N;
    private static Node[] nodes;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        nodes = new Node[N];

        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());
            nodes[i] = new Node(start, end);
        }


        Arrays.sort(nodes);

        int cnt = 0, prevEndTime = 0;
        for (int i = 0; i < N; i++) {
            Node cur = nodes[i];
            if (prevEndTime <= cur.start) {
                prevEndTime = cur.end;
                cnt++;
            }
        }

        System.out.println(cnt);
    }

    private static class Node implements Comparable<Node> {
        int start, end;

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

        @Override
        public int compareTo(Node o) {
            return this.end == o.end ? this.start - o.start : this.end - o.end;
        }
    }
}