[백준] 1931번:회의실 배정 (Java 자바)

문제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

풀이 및 소스코드

 

먼저 회의가 끝나는 시간을 기준으로 오름차순으로 정렬한다.

(1,2) (3,3) (2,3) 이렇게 회의 시간이 주어졌다면,

회의가 끝나는 시간을 기준으로만 오름차순으로 정렬하게 되면 최대 회의 개수가 (1,2) (3,3) 2개가 출력되는 오류가 생긴다.

시작하자마자 끝나는 회의가 존재하기 때문이다.

따라서, 끝나는 시간이 같다면 시작하는 시간을 기준으로도 오름차순을 정렬해줘야 한다.

그렇게되면,

(1,2) (2,3) (3,3) 으로 정렬이 되기 때문에 올바른 답이 나올 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		
		Time[] room = new Time[n];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			room[i] = new Time(a, b);
		}
		Arrays.sort(room);
		
		int res = 1;
		int tmp = room[0].end;
		for(int i=1;i<n;i++) {
			if(tmp <= room[i].start) {
				res+=1;
				tmp = room[i].end;
			}
		}
		System.out.println(res);
		
	}
}
class Time implements Comparable<Time>{
	int start;
	int end;
	
	public Time(int start, int end) {
		super();
		this.start = start;
		this.end = end;
	}

	@Override
	public int compareTo(Time o) {
		if(this.end - o.end > 0 || this.end - o.end < 0){
			return this.end - o.end; //양수면 바뀜 오름차순.
		}
		else {
			return this.start - o.start;
		}
		// TODO Auto-generated method stub
	}
	
	
}