[백준] 회의실 배정(1931)

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

한 개의 회의실에 가능한 많이 회의를 잡을 수 있도록 구하는 것이 문제이다.

예제 입력을 기준으로 잘 생각해보면, 정렬을 아래와 같이 진행해야 한다는 점을 파악할 수 있다.

1. 끝나는 시간을 기준으로 오름차순 정렬하되, 만약 끝나는 시간이 동일할 경우 시작 시간이 작은 것부터 오름차순 정렬

   문제에서 회의의 시작시간과 끝나는 시간이 같을 수도 있으며, 끝나는 것과 동시에 다음 회의가 시작될 수 있다고 했다.

   e.g. (2, 2), (1, 2)가 있다고 가정하면 (1, 2)를 먼저 배정한 다음, (2, 2)를 배정하여 총 2 라고 출력해야 한다는 점에 유의하자.

2. 그 이후 끝나는 시간이 가장 작은 것을 하나 선택한다.

3. 현재 뽑은 회의 시작 시간이 직전에 끝난 회의 끝 시간보다 크거나 같을 경우 count 값을 증가시킨다.

이를 적용하기 위해 아래와 같이 람다식으로 compare 메서드를 오버라이딩해야 한다.

PriorityQueue<Conference> conf = new PriorityQueue<>(
		(o1, o2) -> {
        if (o1.end == o2.end) {
        	return o1.start - o2.start;
		}
        return o1.end - o2.end;
	});

예제 입력을 기준으로 3번 코드를 실행한 흐름도는 다음과 같다.

1 >= 0
cnt++, cur_end = 4

3 >= 4

0 >= 4

5 >= 4
cnt++, cur_end = 7

3 >= 7

5 >= 7

6 >= 7

8 >= 7
cnt++, cur_end = 11

8 >= 11

8 >= 11

2 >= 11

12 >= 11
cnt++, cur_end = 14

cnt는 4가 됨

따라서 전체 소스코드는 다음과 같다.

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

public class P_1931 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Conference> conf = new PriorityQueue<>(
                (o1, o2) -> {
                    if (o1.end == o2.end) {
                        return o1.start - o2.start;
                    }
                    return o1.end - o2.end;
                });

        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());

            conf.add(new Conference(start, end));
        }

        int count = 0;
        int currentEndTime = 0;
        while (!conf.isEmpty()) {
            Conference now = conf.poll();

            if (now.start >= currentEndTime) {
                count++;
                currentEndTime = now.end;
            }
        }

        System.out.println(count);
    }
}

class Conference {
    int start;
    int end;

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