99클럽 코테 스터디 19일차 TIL 그리디(강의실)

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

 

<아이디어>

뒤에 오는 강의의 시작 시간이 앞 강의에 포함되는 지 확인하면 되는 문제이다.

(단, 여러 강의실이 사용되고, 각 강의실마다 끝나는 시간이 다르니 이 경우를 모두 확인해 주어야 한다.)

1. 우선 1차로 강의 시작시간을 오름차순으로 정렬하고, 시작시간이 같을 땐 종료시간을 기준으로 오름차순 정렬한다.(람다식 사용)

2. 첫 번째 강의의 종료 시간을 pq에 넣는다. (가장 빨리 끝나는 강의실에 다음 강의를 배정해야하므로 우선순위큐를 사용했다.)

3. 이전 강의의 가장 빨리 끝나는 시간이 현재 강의의 시작 시간보다 클 경우 (강의 시간이 겹칠경우) 강의실 수(cnt)를 1 증가시키고, 이전 강의 종료 시간과 현재 강의 종료 시간을 모두 pq에 넣는다.

4. 이전 강의의 가장 빨리 끝나는 시간이 현재 강의의 시작 시간보다 작을 경우 (강의 시간이 겹치지 않을 경우) 현재 강의 종료 시간만 pq에 넣는다. (이전 강의 종료 시간은 이미 poll 되어 pq에 없다)

5. 모든 강의의 강의실을 배정한 후, cnt를 출력하면 답!

 

<제출 코드>

package Study.Week03;

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

public class Day19_BOJ_1374_강의실 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(arr[0][1]);
        int cnt = 1;
        for(int i=1; i<n; i++){
            int s = arr[i][0];
            int e = arr[i][1];
            if(!pq.isEmpty()){
                int p = pq.poll();
                if(s < p){
                    cnt++;
                    pq.add(p);
                    pq.add(e);
                }else pq.add(e);
            }
        }
        System.out.println(cnt);
    }
}