[알고리즘] 백준 > #11000. 강의실 배정

문제링크

백준 #11000. 강의실 배정

풀이방법

이 문제도 잘~ 생각해보면 그리디 알고리즘으로 해결가능한 문제죠? 한 강의실을 사용하는 수업 간의 텀을 짧게 해주면 됩니다! 그럼 최소의 강의실로 모든 수업을 들을 수 있죠~

코드의 흐름은 다음과 같습니다.
#1. 수업 정보를 모두 입력받고 수업시작시간을 오름차순으로 정렬
#2. 정렬된 상태의 수업들을 돌며 강의실 배정
강의실 배정 시에는 다음 케이스들이 존재합니다!

• 아직 아무런 강의실이 없는 경우 -> 한 강의실을 새로 가져와 수업 배정 (사용강의실++)
• 가장 빨리 끝나는 수업 다음에 들어갈 수 있는 경우 -> 그 강의실을 사용
• 사용중인 강의실 뒤로 들어가지 못하는 경우-> 새 강의실을 가져와 수업 배정 (사용강의실++)

#1의 수업정보들은 그냥 LinkedList에 저장했습니다! 다 넣고 한번의 정렬하고 순서대로 접근하기 때문에 LinkedList가 적합하다고 생각했습니다.

#2에서는 아무런 강의실이 없는 경우 / 가장 빨리 끝나는 수업을 판단해야했는데요, 이를 위해 각 강의실 수업이 끝나는 시간을 자료구조에 저장했습니다. 이 단계에서는 pop, push, sort 연산이 매번 일어나기 때문에 우선순위큐를 사용했습니다. (push 시 sort -> O(logn), pop -> O(1))

코드

import java.util.*;

public class BOJ11000 {
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        List<Class> classes = new LinkedList<>();
        while(--n >= 0) classes.add(new Class(sc.nextInt(), sc.nextInt()));
        Collections.sort(classes);

        int count = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (Class c: classes) {
            if (pq.isEmpty()) count++; // 아무런 강의실이 없는 경우 -> 첫 수업으로 넣음
            else if (pq.peek() <= c.startTime) pq.poll(); // 가장 빨리 끝나는 수업다음에 들어갈 수 있는 경우 -> 그 수업뒤로 넣어줌
            else count++; // 사용중인 강의실 뒤로 들어가지 못하는 경우 -> 새 강의실

            pq.offer(c.endTime);
        }

        System.out.print(count);
    }
}

class Class implements Comparable<Class> {
    public int startTime;
    public int endTime;

    public Class(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Class o) {
        return this.startTime - o.startTime;
    }
}