[그리디] 백준 1931번 회의실 배정(Java)

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

1931번: 회의실 배정

📚 문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만드려한다.

각 회의 i에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

 

📝 문제 해결

겹치지 않은 시간에 대해 종료시간이 빠르면 더 많은 회의를 할 수 있으므로

종료시간을 기준으로 정렬해 준 뒤

먼저 빨리 끝나는 것을 선택하고 (a)

이전 종료시간에 대해 겹치는 회의를 제외한 다음 남은 회의를 선택한다. (b)

💡 만약 종료시간이 같은 경우에는 시작시간이 빠른 순으로 정렬해줘야한다!

 

💻 코드

import java.util.*;
 
public class BOJ1931 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int[][] time = new int[N][2];
		
		for(int i = 0; i < N; i++) {
			time[i][0] = in.nextInt();
			time[i][1] = in.nextInt();
		}
		
		Arrays.sort(time, new Comparator<int[]>() {
		
			@Override
			public int compare(int[] o1, int[] o2) {
				
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
				
				return o1[1] - o2[1];
			}
 
		});
		
		int count = 0;
		int end = 0;
		
		for(int i = 0; i < N; i++) {
			if(end <= time[i][0]) {
				end = time[i][1];
				count++;
			}
		}
		System.out.println(count);
	}
}