[백준 1931] 회의실 배정

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

1931번: 회의실 배정

---

살면서 코테에 응시한 적은 몇번 없지만

 

이 회의실 배정 유형이 자꾸 나오는 것 같아서 이번 기회에 관련 유형을 모조리 정리해보려한다.

 

1931 회의실 배정 문제는 그 중에서도 가장 기본적인 문제이다.

 

문제 상황은 단순하다.

 

회의실이 하나 존재하고,

 

시작시간, 끝시간으로 이루어진 회의 시간표들이 N 개 주어질 때

 

최대한 많이 진행할 수 있는 회의의 개수를 구하면 된다.

 

즉,

 

회의실이 사용되지 않는 시간을 최소화해야 한다는 것이다.

 

어떻게 풀 수 있을까..?

 

생각해보면 쉽게 떠올릴 수 있다.

 

그냥!

 

회의 종료 시간이 빠른 순으로 배정하면 된다.

 

예제 상황을 통해 생각해보자.

 

 

예제 1 케이스는 이미 정렬된 상태로 주어진다.

 

그럼 정렬했다고 치고,

 

맨 처음에는 

 

(1, 4) 를 배정할 것이다.

 

그 다음에는?

 

회의 리스트를 탐색하면서,

 

이전에 회의의 끝시간 이후에 시작하는 회의를 배정하면 된다.

 

위 경우에는 (5,7) 이 해당할 것이다. 

 

그 다음은 아무래도 8, 11 이 적절할 것이고

 

그 다음은 12, 14 를 배정해야 할 것이다.

 

최종 출력은 회의를 배정한 개수를 반환하면 된다.

 

회의를 배정한 개수를 반환하기 위해서는,

 

변수를 하나 두고 계속 카운팅을 해도 되지만

 

나는 stack 을 만들어두고

 

stack 에 "이전 회의의 끝나는 시간" 을 push 하는 방법을 사용했다.

 

이렇게하면 stack 의 size 가 답이 된다.

 

코드는 아래와 같다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;
        Stack<Integer> st = new Stack<>();
        ArrayList<int[]> table = new ArrayList<>();
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(stk.nextToken());
            int e = Integer.parseInt(stk.nextToken());
            table.add(new int[]{s, e});
        }

        // 끝나는 시간이 빠른 순으로 정렬
        table.sort((int[] a, int[] b) -> {
            if (a[1] == b[1]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });

        for (int i = 0; i < table.size(); i++) {
            int[] now = table.get(i);
            if (st.isEmpty()) {
                st.add(now[1]);
            } else if (now[0] >= st.peek()) {
                st.add(now[1]);
            }
        }
        System.out.println(st.size());

        bw.flush();
        bw.close();
    }
}