[알고리즘] Meeting Rooms II

Problem

Key Point

• Priority Queue
  • 일반적인 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다.
  • 우선순위 큐는 들어간 순서에 상관없이 일정한 규칙에 따라 우선 순위를 선정하고 우선 순위가 가장 높은 데이터가 먼저 나오게 된다.
  • Java는 기본적으로 오름차순이고 내림차순으로 정렬이 필요한 경우 Comparator 클래스나 Comparable 인터페이스를 이용한다.

// 종료 시간을 기준으로 오름차순
Queue<Interval> priorityQueue = new PriorityQueue<>((o1, o2) -> o1.getEnd() - o2.getEnd()));

Code

public class MeetingRoom2 {
    public int solution(Interval[] intervals) {
        if(intervals == null  || intervals.length == 0) return 0;

        // Start 시간으로 정렬
        Arrays.sort(intervals, (o1, o2) -> o1.getStart() - o2.getStart());

        // Priority Queue 생성
        Queue<Interval> pq = new PriorityQueue<>(((o1, o2) -> o1.getEnd()-o2.getEnd()));

        pq.offer(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
        	// 회의 종료 시간보다 큰 시작 시간이 있는 경우 하나의 회의실을 사용할 수 있으므로 큐에서 삭제
            if (pq.peek().getEnd() <= intervals[i].getStart()) {
                pq.poll();
            }
            pq.offer(intervals[i]);
        }
        return pq.size();
    }

    public static void main(String[] args) {

        Interval[] intervals = new Interval[]{new Interval(0, 30), new Interval(4, 9), new Interval(10, 16), new Interval(5, 15)};
        MeetingRoom2 meetingRoom2 = new MeetingRoom2();
        System.out.println(meetingRoom2.solution(intervals));
    }
}