[알고리즘] meeting Room2 (java 풀이)

leetCode 무료로 제공하는 문제가 아니기때문에 문제는 업로드할 수 없지만, 

meeting Room1 문제와 매우 유사한 문제로 필요한 회의실의 개수를 리턴하는 문제이다.

 

 

class Interval{
	int start, end;
	Interval(){
		this.start =0;
		this.end =0;
	}
	Interval(int s, int e){
		this.start = s;
		this.end = e;
	}
}
public class MeetingRoom2 {
	
	public static void main(String[] args) {
		MeetingRoom2 a = new MeetingRoom2();
		Interval in1 = new Interval(5,10);
		Interval in2 = new Interval(15,20);
		Interval in3 = new Interval(0,30);
		Interval in4 = new Interval(15,20);
		Interval in5 = new Interval(18,20);
		Interval[] intervals = {in1,in2,in3,in4,in5};
		System.out.println(a.solve(intervals));
	}
	public int solve(Interval[] intervals) {
		if(intervals == null || intervals.length==0)
			return 0;
		Arrays.sort(intervals, Comp);
		Queue<Interval> heap = new PriorityQueue<Interval>(intervals.length, Comp2);
		
		heap.offer(intervals[0]);
		
		for(int i=1; i<intervals.length; i++) {
			Interval interval = heap.peek();
			if( interval.end <= intervals[i].start  ) {
				interval.end = intervals[i].end;
			}else {
				heap.offer(intervals[i]);
			}
//			 heap.offer(interval);
		}
		return heap.size();
		
		
		
	}
	
	Comparator<Interval> Comp2 = new Comparator<Interval>() {
		@Override
		public int compare(Interval o1, Interval o2) {
			// TODO Auto-generated method stub
			return o1.end - o2.end;
		}
	};
	
	Comparator<Interval> Comp = new Comparator<Interval>() {
		@Override
		public int compare(Interval o1, Interval o2) {
			// TODO Auto-generated method stub
			return o1.start - o2.start;
		}
	};
}

 

이 문제는 meeting Room1과 다르게, 겹치지 않는 부분을 합쳐버리면 된다.

회의 시작순서로 정렬을 하고, 우선순위 큐에는 회의가 끝나는 시간을 기준으로 정렬을 해줘야 

바로 다음 회의를 진행할 수 있는지 여부를 판단할 수 있다.