백준 1379번 강의실 2

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

 

N개의 강의의 번호, 시작 시간, 종료 시간이 주어질 때, 강의가 겹치지 않게 진행할 수 있는 강의실의 최소 갯수와 각 강의의 교실을 출력하는 문제이다. 1374번 강의실 문제처럼 시작 순서대로 강의를 진행하면서 이용 가능한 강의실 번호를 종료시간 기준 우선순위 큐를 통해 가능한 강의실을 그 중 가장 작은 강의실을 부여하는 방식으로 해결하였다.

 

 

강의를 위한 클래스는 강의번호, 시작시간, 종료시간을 가지며, 시작 시간으로 정렬하기 위해 Comparable을 implement 하였다.

static class Lecture implements Comparable<Lecture> {
    
    int id, start, end;
    
    Lecture(int id, int start, int end) {
        this.id = id;
        this.start = start;
        this.end = end;
    }
    
    @Override
    public int compareTo(Lecture o) {
        return this.start - o.start;
    }
}

 

 

강의실은 종료시간, 강의실 번호를 가지며, 종료 시간으로 정렬하기 위해 Comparable을 implement 하였다.

static class Room implements Comparable<Room> {
    
    int endTime, roomNum;
    
    Room(int endTime, int roomNum) {
        this.endTime = endTime;
        this.roomNum = roomNum;
    }
    
    @Override
    public int compareTo(Room o) {
        return this.endTime - o.endTime;
    }
}

 

 

강의 정보를 입력받아 배열에 저장하였으며 이를 Arrays.sort를 이용하여 시작 시간순으로 정렬하였다.

Lecture[] lectures = new Lecture[n];
for (int i = 0; i < n; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    lectures[i] = new Lecture(
            Integer.parseInt(st.nextToken()),
            Integer.parseInt(st.nextToken()),
            Integer.parseInt(st.nextToken())
    );
}
br.close();
Arrays.sort(lectures);

 

 

이후 시작 시간순으로 강의를 강의실에 배치한다. 현재 강의의 시작 시간 기준 비게 되는 강의실을 찾고 그 중 가장 작은 강의실 번호를 가진 강의실을 현재 강의에 부여한다. 이용 가능한 강의실이 없다면 꽉 차 있으므로 최대 강의실번호 +1 를 부여한 후 최대 강의실번호를 1 증가시킨다. 사용 가능한 강의실을 찾기 위해 현재 강의를 진행중인 강의실 우선순위 큐와 이용 가능한 강의실 번호들의 우선순위 큐를 이용하였다.

PriorityQueue<Room> endPQ = new PriorityQueue<>();
PriorityQueue<Integer> availableRooms = new PriorityQueue<>();

int[] resultRoom = new int[n + 1];
int maxRoomId = 0;

for (Lecture cur : lectures) {
    while (!endPQ.isEmpty() && endPQ.peek().endTime <= cur.start) {
        availableRooms.add(endPQ.poll().roomNum);
    }
    
    int assignedRoom;
    if (availableRooms.isEmpty()) {
        assignedRoom = ++maxRoomId;
    } else {
        assignedRoom = availableRooms.poll();
    }
    
    resultRoom[cur.id] = assignedRoom;
    endPQ.add(new Room(cur.end, assignedRoom));
}

 

 

결과 코드는 다음과 같다.

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 강의실1379 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Lecture[] lectures = new Lecture[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            lectures[i] = new Lecture(
                    Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken())
            );
        }
        br.close();
        Arrays.sort(lectures);
        
        PriorityQueue<Room> endPQ = new PriorityQueue<>();
        PriorityQueue<Integer> availableRooms = new PriorityQueue<>();
        
        int[] resultRoom = new int[n + 1];
        int maxRoomId = 0;
        
        for (Lecture cur : lectures) {
            while (!endPQ.isEmpty() && endPQ.peek().endTime <= cur.start) {
                availableRooms.add(endPQ.poll().roomNum);
            }
            
            int assignedRoom;
            if (availableRooms.isEmpty()) {
                assignedRoom = ++maxRoomId;
            } else {
                assignedRoom = availableRooms.poll();
            }
            
            resultRoom[cur.id] = assignedRoom;
            endPQ.add(new Room(cur.end, assignedRoom));
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(maxRoomId).append('\n');
        for (int i = 1; i <= n; i++) {
            sb.append(resultRoom[i]).append('\n');
        }
        System.out.print(sb);
    }
    
    static class Lecture implements Comparable<Lecture> {
        
        int id, start, end;
        
        Lecture(int id, int start, int end) {
            this.id = id;
            this.start = start;
            this.end = end;
        }
        
        @Override
        public int compareTo(Lecture o) {
            return this.start - o.start;
        }
    }
    
    static class Room implements Comparable<Room> {
        
        int endTime, roomNum;
        
        Room(int endTime, int roomNum) {
            this.endTime = endTime;
            this.roomNum = roomNum;
        }
        
        @Override
        public int compareTo(Room o) {
            return this.endTime - o.endTime;
        }
    }
}