백준 회의실 배정 성공(1931)

 

그리디를 이용한 방배정 문제

 

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

1931번: 회의실 배정

 

간단하게 빨리 끝나는 회의실 순으로 최적의 해를 구하면 된다.

 

그리고 빨리 시작하는 회의실을 잡아야하는데 그게 예시로 5-10, 10-10 두개의 회의를 사용해야하기 때문에...? 저게 말이되나...

 

일단 그렇다

 

package greedy;

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

/**
 * https://www.acmicpc.net/problem/1931
 */
public class Q1931 {

    public static void main(String[] args) throws IOException {
        greedy();
    }

    public static void greedy() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(((o1, o2) -> {
            if (o1[1] == o2[1]) {
                return o1[0] - o2[0];
            } else {
                return o1[1] - o2[1];
            }
        }));

        for (int i=0 ; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            priorityQueue.add(new int[]{start, end});
        }

        int time = 0;
        int count = 0;

        while (!priorityQueue.isEmpty()) {
            int[] table = priorityQueue.poll();
            int start = table[0];
            int end =  table[1];
            if (time <= start && time <= end) {
                time = end;
                count ++;
            }
        }

        System.out.println(count);

    }
}

 

결과