MeetingRoom2

알고리즘 1. sorting by start time 2. create a PriorityQueue by end time. 3. before.end <= after.start : 합치기 before.end > after.start : 회의실 1개 추가 필요. 4. 최종적으로 heap의 크기가 정답(필요한 미팅룸 갯수)가 된다.

필요한 자료구조 : Heap

: BST 로 구성된다. 시간복잡도는 nlogn end시간으로 오름차순으로 MinHeap을 구성하게 되면 아래와 같다.

package java_basic;

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

class Interval {
	int start;
	int end;
	Interval() {start = 0; end = 0;}
	Interval(int s, int e) {start = s; end = e;}
}
public class MeetingRoom2 {

	public static void main(String[] args) {
		Interval in1 = new Interval(5,10);
		Interval in2 = new Interval(0,30);
		Interval in3 = new Interval(15,25);

		Interval[] intervals = {in1,in2,in3};
		
		MeetingRoom2 MR2 = new MeetingRoom2();
		/*int result = MR2.solve(intervals);
		
		System.out.println("필요한 미팅룸 갯수 :" + result);*/
		System.out.println(MR2.solve(intervals));
	}

	public int solve(Interval[] intervals) {
		if(intervals == null || intervals.length == 0) return 0;
		
		
		//알고리즘 구현.
		//1. start time으로 정렬. 받은 intervals가 배열이니까
		Arrays.sort(intervals,(a,b)->(a.start-b.start));
		
		//2. end time으로 정렬, 우선순위큐 MinHeap.
		Queue<Interval> minHeap = new PriorityQueue<Interval>(intervals.length,Comp);
		
		minHeap.offer(intervals[0]);
		for(int i=1; i <= intervals.length;i++) {
			Interval interval = minHeap.poll();//else인 경우 두개가 필요한데 poll하면 어떻함.
			if(interval.end <= intervals[i].start) {//하나로 합친다! 
				interval.end = Math.max(interval.end, intervals[i].end);
			} else {//미팅룸 하나 더 생성(힙에 노드 하나 추가) 
				minHeap.offer(intervals[i]);
			}
			minHeap.offer(interval);
		}
		return minHeap.size();
	}
	Comparator Comp = new Comparator<Interval>() {
		public int compare(Interval a, Interval b) {
			return a.end - b.end;
		}
	};
}