BOJ 1931 회의실배정

 

1931번: 회의실배정

단순한 그리디 알고리즘으로 풀린다. 

회의시간이 주어졌을 때

1)끝나는 시간이 가장 빠른 회의를 먼저 선택

2)해당 회의시간과 겹치지 않는 회의가 나오면 그 회의를 또 선택

.. 이렇게 반복해서 회의 선택할 때마다 +1 을 해주면 최대로 진행할 수 있는 회의 수가 된다.

 

하지만 해당 문제에서 주어지는 회의시간이 끝나는 시간 대로 정렬되지 않았기 때문에 먼저 끝나는 시간 별로 들어온 회의 정보를 정렬해준다. 

그렇다고 끝나는 시간별로만 정렬을 해주면 틀린다. 왜냐하면

8시 시작 8시 끝 5시 시작 8시 끝 이렇게 주어진 회의의 경우, 정렬하였을 때도 8-8 5-8 이렇게 정렬되기 때문에

8-8 회의를 진행하고 5-8을 진행할 수 없다고 판단하게 된다. (왜냐하면 첫번째 회의의 끝나는 시간 8 보다 두번째 회의의 시작하는 시간 5 이 더 작기때문이다. ) 하지만 실제로는 5-8 8-8 이런식으로 두 회의를 진행할 수 있다.

 

따라서 , 정렬조건을 넣어준다.

두 요소의 끝나는 시간이 같은 경우에는, 시작하는 시간대로 정렬을 해주어야한다.

 

아래는 전체 자바소스이다.

import java.util.*;
import java.io.*;

class pair implements Comparable<pair>{
	pair(int start, int end){
		this.start=start;
		this.end=end;
	}
	pair(){}
	
	
	int start;
	int end;
	@Override 
	// 끝나는 시간 (end)으로 오름차순 정렬, 끝나는 시간이 같다면 시작시간 (start)로 정렬해주어야 한다.
	public int compareTo(pair arg) {
		if(this.end < arg.end ) return -1;
		else if(this.end>arg.end ) return 1;
		else if (this.end == arg.end) {
			if(this.start < arg.start) return -1;
			else if(this.start > arg.start) return 1;
		}
		return 0;
	}
}

public class Main {	
	static pair[] info; 
	static int maxnum=1;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(stk.nextToken());
		info = new pair[n]; 
		for(int i=0;i<n; i++) {
			stk = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(stk.nextToken());
			int end = Integer.parseInt(stk.nextToken());
			info[i]=new pair(start,end); 
		}
		
		Arrays.parallelSort(info); // 소팅 (끝나는 시간 별로 ) 
		solve(n);
		System.out.println(maxnum);
	}
	
	private static void solve(int n) {
		pair now = info[0]; //가장 빨리 끝나는 회의 먼저 저장 
		for(int i=1; i<n; i++) { 
			if(info[i].start >= now.end){ //다음 회의의 시작시간이 현재 하고 있는 회의의 끝나는 시간과 같거나 
				                          //넘어가는 경우 새로운 회의 시작 
				now = info[i];
				maxnum++;
			}
		}
		
	}
}