MeetingRoom2

• 회의의 시작과 끝이 주어짐
• 총 회의에서 사용될 회의실 수를 리턴해라.
• intervals 의 length 가 0 이 아닌이상 1개의 방은 무조건 있음
• 이후 start, end를 비교해서 겹치면 방 추가함

public class MeetingRoom2 {
    public static void main(String[] args) {
        Interval interval1 = new Interval(0, 30);
        Interval interval2 = new Interval(5, 10);
        Interval interval3 = new Interval(15, 20);
        Interval interval4 = new Interval(7,10);
        Interval interval5 = new Interval(2, 4);
        Interval[] intervals = new Interval[]{interval1,interval2,interval3,interval4,interval5};

        int answer = solve(intervals);
        System.out.println(answer);
    }

    private static int solve(Interval[] intervals) {
        Arrays.sort(intervals, (o1,o2) -> o1.start - o2.start);
        int result = 1;
        for(int i=1; i<intervals.length; i++){
            if(intervals[i-1].end > intervals[i].start){
                result ++;
            }
        }
        return result;
    }


}

---

풀이법

 

우선순위 큐는 정말 중요하다고 한다. 사용해보는 연습을 해야겠다.

• 우선순위 큐를 사용.
• Start 를 기준으로 소팅
• End 를 기준으로 다시 minHeap 에 넣어줌 즉 내림차순으로 우선순위 큐 구현
• 큐에 값을 넣는다.
• 다음 원소의 start 값이 end 보다 <= 라면 poll() 빼내고 원소 값을 넣는다. 왜..? size로 리턴할 것이므로
• 사이즈를 리턴한다.

public class MeetingRoom2Teaching {
    public static void main(String[] args) {
    	Interval interval1 = new Interval(0, 30);
        Interval interval2 = new Interval(5, 10);
        Interval interval3 = new Interval(15, 20);
        Interval interval4 = new Interval(7,10);
        Interval interval5 = new Interval(2, 4);
        Interval[] intervals = new Interval[]{interval1,interval2,interval3,interval4,interval5};

        int answer = solve(intervals);
        System.out.println(answer);
    }

	private static int solve(Interval[] intervals) {
	if(intervals == null && intervals.length ==0) 
		return 0;
	
		Arrays.sort(intervals, (o1, o2) -> o1.start - o2.start);
		
		//사이즈와 우선순위를 정했다.
		Queue<Interval> minHeap = new PriorityQueue<Interval>(intervals.length, (o1, o2) -> o1.end - o2.end);
		int max = 0;
		
		for(int i=0; i<intervals.length; i++) {
			
			// 큐가 비었거나 , end 타임보다 start 타임이 크다면 방 1개로 커버 됨
			while(! minHeap.isEmpty() && minHeap.peek().end <= intervals[i].start) {
				minHeap.poll();// size로 비교할 것이므로 빼낸다.
			}
			
			minHeap.offer(intervals[i]);// 0 30 , 5 10
			max = Math.max(max, minHeap.size());
		}
		return max;
	}
}