백준 1379 (강의실 2) - java

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

1379번: 강의실 2

 

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실 수 K와, 각 강의마다 강의실을 배정하는 프로그램을 작성하시오.

 

유형 : 그리디 + 정렬

 

접근 방식

• 기존 강의실 문제에서 각 수업이 배정되는 강의실의 번호를 추가 출력하는 문제이다.
• 문제 조건에 의하면 가장 적은 수의 강의실 개수를 사용해야 한다. 즉 수업을 뒤에 붙힐 수 있는 만큼 붙혀야 한다는 것이다.
• 정렬 조건
  • 강의의 시작 시간이 작은 순 -> 빨리 시작하는 것부터 채워야 한다.
  • 강의가 끝나는 시간이 작은 순 -> 뒤에 오는 수업을 이어 붙힐 수 있다면 붙혀야 한다.
• 강의실
  • 끝나는 순이 빠른 (오름차순) 순으로 끝나는 시간만 저장
• 동작
  • 위 순으로 정렬된 우선 순위 큐에서 가장 처음의 강의를 확인한다.
    • 강의실 큐가 비어 있는 경우
      • 첫번째 강의실 배정
    • 가장 빨리 끝나는 강의 (우선순위 큐의 peek)
      • 다음 강의가 더 늦게 시작하는 경우 -> 이어붙힌다. (기존 강의실 배정)
      • 더 빨리 시작하는 경우 -> 새로운 강의실 배정

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n = 0;



    public static void main(String[] args) throws Exception {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int[] result = new int[n+1];
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> {
                    if(x.s == y.s)
                        return x.e - y.e;

                    return x.s - y.s;
                }
        );

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());

            int num = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            pq.add(new Node(num,s,e));
        }


        PriorityQueue<Room> room = new PriorityQueue<>(
                (x,y) -> x.e - y.e
        );


        while(!pq.isEmpty()){
            Node cur  = pq.poll();

            if(room.isEmpty()){
               room.add(new Room(1,cur.e));
               result[cur.num] = 1;
            }else{
                if(room.peek().e <= cur.s){
                    result[cur.num] = room.peek().num;
                    room.poll();
                    room.add(new Room(result[cur.num],cur.e));
                }else{
                    result[cur.num] = room.size() + 1;
                    room.add(new Room(result[cur.num],cur.e));
                }
            }
        }

        sb.append(room.size()+"\n");

        for(int i=1;i<=n;i++){
            sb.append(result[i]+"\n");
        }

        System.out.print(sb);
        br.close();
    }
}
class Room{
    int num;
    int e;

    Room(int num,int e){
        this.num  = num;
        this.e = e;
    }
}
class Node{
    int num;
    int s;
    int e;

    Node(int num,int s,int e){
        this.num = num;
        this.s = s;
        this.e = e;
    }
}