[백준] 1931 : 회의실 배정 JAVA 풀이

 

종료시간이 빠른 순으로 정렬해서 푸는

기본적인 그리디문제처럼 보이지만 주의해야 할 점이 있다.

 

그저 종료시간이 빠른 순으로 정렬하기만 해서는

3

3 3

3 3

1 3

이 입력으로 주어졌을 때

올바른 출력값은 3인데 2가 출력되는 문제가 발생한다.

 

종료시간은 같은데 시작시간은 더 빠른 회의가 제대로 처리되지 않는 것이다.

 

이 문제를 해결하는 방법은 간단하다.

종료시간이 빠른 순으로 정렬하되, 

종료시간이 같을 때는 시작시간이 빠른 순으로 정렬을 하는 것이다.

 

이렇게 정렬한 뒤에는 한 회의의 시작시간 >= 현재 진행된 시간이면 회의를 하도록

코드를 짜주면 된다.

import java.io.*;
import java.util.*;
public class Main {

	static class Meeting{
		int start;
		int end;
		Meeting(int start, int end){
			this.start = start;
			this.end = end;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Meeting> list = new ArrayList<>();
		
		for(int i=0;i<N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			list.add(new Meeting(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));			
		}
		
		list.sort((o1, o2)->{
			if(o1.end==o2.end) {
				return o1.start-o2.start;
			}
			return o1.end-o2.end;
		});

		int cnt = 0;
		int time = -1;
		
		for(int i=0;i<list.size();i++) {
			Meeting m = list.get(i);
			
			if(time<=m.start) {
				time = m.end;
				cnt++;
			}
		}
		System.out.println(cnt);
	}

}