[BOJ] 11000

[HyomK]

백준 11000 강의실 배정
[문제유형] 그리디, 우선순위 큐

핵심 코드

  data class Lecture(val start  : Long, val end : Long) : Comparable<Lecture>{
        override fun compareTo(other: Lecture): Int {
            return (start - other.start).toInt()
        }
    }
    val lecture = LinkedList<Lecture>()
    val pq = PriorityQueue<Long>()

 pq.add(lecture.poll().end)
        for(l in lecture){
            if(l.start >=pq.first()){
                //만약 새 강의가 기존 강의보다 늦게 시작하면 더 늦게 끝난것 즉 다음 강의이다
                pq.poll()
                pq.add(l.end)
            }else{
                //새 강의는 일찍 시작하거나 중간이기에 새 강의실 배정
                pq.add(l.end)
            }
        }
 println(pq.size)

우선순위 큐를 이용한 방식이다.

1. 먼저 강의를 시작시간이 빠른 순서대로 정렬한다
2. 큐가 비어있다면 가장 빠른 강의의 끝나는 시간을 큐에 집어 넣는다
3. 정렬한 강의 리스트에서 그 다음으로 빠른 시간의 강의가 나오게 된다
4. 다음 강의의 시작시간이 큐에 담긴 강의의 끝나는 시간보다 늦다면 start >= queue.peek() 그 강의는 다음에 이어서 수업할 수 있기 때문에 큐를 pop하고 해당 강의의 끝나는 시간을 queue에 넣는다
5. 만약 강의의 시작시간이 큐에 담긴 끝나는 시간보다 빠른 경우는 같은 강의실을 쓸 수 없기 때문에 (시작시간 : 7시 , 큐에 담긴 수업 종료시간 : 9시 ) queue 에 바로 끝나는 시간을 넣는다
6. 큐의 수는 곧 필요한 강의실의 수가 된다