백준 1374: 강의실

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

 

시작 시간과 종료 시간이 주어진 강의들을 모두 진행하기 위해 필요한 최소한의 강의실의 갯수를 구하는 문제이다. 강의의 종료와 동시에 다른 강의가 시작할 수 있다. 시작 시간이 빠른 순서부터 강의를 시작하면서 진행중인 강의의 종료 시간과 비교하는 방식으로 문제를 해결하였다.

 

 

진행중인 강의의 수가 현재 이용중인 강의실의 수가 되며 넣은 후 최대값을 비교하여 모든 강의를 진행할 수 있는 강의실의 최소 갯수를 구하였다. 강의를 넣고 빼는 방법은 다음과 같다. 시작 시간이 빠른 순서부터 강의를 시작하면서 진행중인 강의 중 빠른 종료 시간 순으로 비교하여 종료 시간이 더 빠르거나 같은 경우 새로운 강의가 시작할 시간에 해당 강의들은 종료 되었음을 의미하며여 진행중인 강의 목록에서 제거한 후, 새 강의를 넣는다. 반대의 경우는 아직 진행중임을 의미하여 새 강의를 강의 목록에 넣는다. 아래의 이미지를 참고하면 좋다.(AI를 이용하여 그림을 그렸다)

 

 

구현 방식은 다음과 같다. 시작 시간에 대한 우선순위 큐와 종료 시간에 대한 우선순위 큐를 이용하여 시작 시간 순서대로 강의를 종료 시간 우선순위 큐에 넣어 강의를 진행하며, 넣기 전에 종료 시간 우선순위 큐에 새로 시작하는 강의보다 빨리 끝나거나 동시에 끝나는 강의들을 전부 제거한다. 그 후, 진행시키고 필요한 강의실 수를 구한다.

PriorityQueue<Lecture> inputPQ = new PriorityQueue<>(new Comparator<Lecture>() {
    @Override
    public int compare(Lecture o1, Lecture o2) {
        return Long.compare(o1.inputTime, o2.inputTime);
    }
});

for (int i = 0; i < n; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int number = Integer.parseInt(st.nextToken());
    long inputTime = Long.parseLong(st.nextToken()), endTime = Long.parseLong(st.nextToken());
    inputPQ.add(new Lecture(inputTime, endTime));
}

PriorityQueue<Lecture> endPQ = new PriorityQueue<>(new Comparator<Lecture>() {
    @Override
    public int compare(Lecture o1, Lecture o2) {
        return Long.compare(o1.endTime, o2.endTime);
    }
});
long max = 0L;
while (!inputPQ.isEmpty()) {
    Lecture current = inputPQ.remove();
    while (!endPQ.isEmpty()) {
        if (endPQ.peek().endTime > current.inputTime) {
            break;
        }
        endPQ.remove();
    }
    endPQ.add(current);
    max = Math.max(max, endPQ.size());
}

 

 

결과 코드는 다음과 같다.

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

public class 강의실1374 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Lecture> inputPQ = new PriorityQueue<>(new Comparator<Lecture>() {
            @Override
            public int compare(Lecture o1, Lecture o2) {
                return Long.compare(o1.inputTime, o2.inputTime);
            }
        });
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken());
            long inputTime = Long.parseLong(st.nextToken()), endTime = Long.parseLong(st.nextToken());
            inputPQ.add(new Lecture(inputTime, endTime));
        }
        
        PriorityQueue<Lecture> endPQ = new PriorityQueue<>(new Comparator<Lecture>() {
            @Override
            public int compare(Lecture o1, Lecture o2) {
                return Long.compare(o1.endTime, o2.endTime);
            }
        });
        long max = 0L;
        while (!inputPQ.isEmpty()) {
            Lecture current = inputPQ.remove();
            while (!endPQ.isEmpty()) {
                if (endPQ.peek().endTime > current.inputTime) {
                    break;
                }
                endPQ.remove();
            }
            endPQ.add(current);
            max = Math.max(max, endPQ.size());
        }
        System.out.print(max);
    }
    
    static class Lecture {
        
        long inputTime, endTime;
        
        public Lecture(long inputTime, long endTime) {
            this.inputTime = inputTime;
            this.endTime = endTime;
        }
    }
}