[JAVA][Array] MeetingRoom2

1. 문제

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei),
find the minimum number of conference rooms required.

Input: [[0,30],[5,10],[15,20]]
Output: 2

Input: [[7,10],[2,4]]
Output: 1

 

2. 문제해설

회의실 사용 시간이 Input으로 주어졌을 때 회의실이 몇 개 필요한지 개수를 구하라

 

3. 코드 포맷

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(7,10);
		Interval in5 = new Interval(2,4);
		Interval[] intervals = {in1,in2,in3,in4,in5};
		System.out.println(a.solve(intervals));
	}

}	

 

4. 접근 방법

1) Input을 회의실 사용시간 기준으로 정렬한다.

2) 회의실의 end시간과 start 시간을 비교해서 만약 end>start인 경우에는 회의실을 1개 더 필요하다는 개념을 활용한다.

 

5. 코드

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(7,10);
		Interval in5 = new Interval(2,4);
		Interval[] intervals = {in1,in2,in3,in4,in5};
		System.out.println(a.solve(intervals));
	}

	private int solve(Interval[] intervals) {
		Stack<Interval> stack = new Stack<Interval>();
		//1. 정렬
		Arrays.sort(intervals,comp);
		print(intervals);
		//2. end와 start를 비교한다.
		for(Interval i : intervals) {
			//회의실이 필요하지 않은 상황
			if(!stack.isEmpty()&&stack.peek().end<i.start) {
				stack.peek().end=i.end;
			}
			else {
				stack.push(i);
			}
		}
		return stack.size();
	}
	
	//정렬
	Comparator<Interval> comp = new Comparator<Interval>() {
		@Override
		public int compare(Interval o1, Interval o2) {
			return o1.start-o2.start;
		}
		
	};
	
	private void print(Interval[] intervals) {
		for(Interval i :intervals) {
			System.out.println(i);
		}
	}

}