MeetingRoom2

 

미팅룸 2 는 지금 사용하고 있는 미팅룸이 존재 하는데

그 사이에 미팅룸이 필요하다면 또 생성하는 것이다.

 

한 미팅룸이 끝나고 다른 미팅룸이 시작 된다면 굳이 미팅룸의 수를 하나 더늘려줄 필요가 없다.

 

처음에는 이해가 안갔는데

쉽게 생각하니 이해가 간다.

 

9시부터 저녁 9시까지 미팅룸1 을 사용하고 있는데

10시부터 3시까지 미팅룸2를 사용하고

4시부터 6시까지 미팅룸을 사용하고 있다면 미팅룸2를 사용하면 된다.

 

 

start 와 end 를 나타내는 미팅룸의 사용시간을 저장하는 클래스를 정의하자.

 

 

 

 

 

 

 

 

 

 

 

 

 

각각 시작 시간과, 끝나는 시간을 넣어주자.

 

 

 

 

 

solve 를 호출하는데

 

 

 

[ solve ]

 당연히 intervals 가 비어 있다면 0 을 반환해준다

 

 

 일단 받은 intervals 을 정렬을 해야지 서로 가까운 시간들끼리 비교를 하겠지

 

 

Comparator<Interval> 을 생성하고 

Override를 해주자.

 

o1.start- o2.start ( 오름차순 )

 

Comparator에 익숙해져서 자주 사용하고 싶다. 습관처럼

 

 

 

 

 

Queue 는 예제에서는 해봤지만 이런식으로 쓰는 거구나. 생각 할 수 있는 계기였다.

heqp 이라는 인스턴스를 생성하고 이제 여기다가 미팅룸을 넣어줄 것이다.

 

Priority Queue 는 우선순위 큐이다.

처음보는 클래스인데, 

우선순위 큐는 먼저 들어온 데이터가 먼저 나가는 일반적인 큐와는 다르게 데이터를 꺼낼 때 우선순위가 가장 높은 데이터가 먼저 나온다.

 

그래서 Peiority Queue 클래스를 사용하는구나,

 

Comp2 는 end를 기준으로

정렬을 한다.

 

 

 

 

 

 

0번째 intervals 를 Queue 에 저장한다.

 

interval 의 길이만큼

for문을 돌린다.

 

 

 

 

 

 

 

 

 

heap에 0번째를 저장해 놓았으니까 poll 해온다.

 

그러면 현재 heap 은 비어있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

방금 poll 한

 

interval 의 end와 비교 대상인 1번째 start 랑 비교를 한다.

근데 end가 크다면 미팅룸이 하나 더 필요하다.

 

아직 미팅룸이 끝나기도 전에 미팅룸을 시작하려고 하는거니까

그러면 heap 에다가 1번째의 intervals 를 offer 해준다.

 

 

 

 

그리고 아까 비교하려고 poll 했던 interval 을 다시 offer 해준다.

 

 

 

 

 

 

 

그러면 heap 의 size 는 2가 된다.

 

 

package soobin;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

class Interval1 {

	int start;
	int end;

	Interval1() {
		start = 0;
		end = 0;
	}

	Interval1(int s, int e) {
		start = s;
		end = e;
	}
}

public class MeetingRoom2 {
	
	public static void main( String[] args ) {
		
		MeetingRoom2 a = new MeetingRoom2();
		
		Interval1 in1 = new Interval1( 5,  10);
		Interval1 in2 = new Interval1( 15, 20);
		Interval1 in3 = new Interval1( 0,  30);
		
		Interval1[] intervals = {in1, in2, in3};
		
		System.out.println(a.solve(intervals));
		
	}

	public int solve(Interval1[] intervals) {
		
		if( intervals == null || intervals.length==0) {
			return 0;
		}
		
		Arrays.sort(intervals, Comp);
		Queue<Interval1> heap = new PriorityQueue<Interval1>( intervals.length, Comp2 );
		
		heap.offer(intervals[0]);
		
		for( int i=1; i<intervals.length; i++) {
			
			Interval1 interval = heap.poll();
			
			if( intervals[i].start < interval.end ){
				// 이미 하고 있는 회의가 끝나는 시간보다 새로운 회의가 더 빨리 시작한다면 회의룸이 하나 더 필요하다
				heap.offer(intervals[i]);
			}
			
			heap.offer(interval);
		}
		return heap.size();
	}
	
	Comparator<Interval1> Comp2 = new Comparator<Interval1>() {
		
		@Override
		public int compare(Interval1 o1, Interval1 o2) {
			// TODO Auto-generated method stub
			return o1.end - o2.end;
		}
	};
	
	Comparator<Interval1> Comp = new Comparator<Interval1>() {
		
		@Override
		public int compare(Interval1 o1, Interval1 o2) {
			// 오름차순
			return  o1.start - o2.start;
		}
	};
}

 

 

이제 진짜 내 궁굼증을 해소해 보아야겠다.

 인스턴스를 여러개 만들고

 

 

 

 

 

 

 

 

 정렬을 한 후에 출력을 해봤다.

 

 결과가 이렇게 나오는데

엥 너무 많은 미팅룸이 필요 할텐데

 

 

 

 

 

 

 

 

 

 

조건을 같거나 크다로 바꾸니까

 

 

 5개가 나오긴 하는데

 

 

 

 

 

 

 

 

 

 

 

 

 

뭔가 불길해

맞는 알고리즘 인가?