[백준 1931] 회의실 배정 - 그리디 알고리즘

지잉지잉 2021. 10. 12. 23:24

문제

풀이

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
	
		Scanner scanner = new Scanner(System.in);
		int count = scanner.nextInt();
		int[][] conversations = new int[count][2];
		for (int i = 0; i < count; i++) {
			conversations[i][0] = scanner.nextInt();
			conversations[i][1] = scanner.nextInt();
		}
		scanner.close();
		
		Arrays.sort(conversations, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
				return o1[1] - o2[1];
			}
		});
		
		
		int answer = 0;
		int[] current = null;
		for (int i = 0; i < count; i++) {
			if (current == null || current[1] <= conversations[i][0]) {
				current = conversations[i];
				answer++;
			}
		}
		
		System.out.println(answer);
	}
	
}

끝나는 시간 순으로 정렬
끝나는 시간이 가장 빠르고, 회의가 끝나자 마자 가장 빨리 시작할 수 있는 회의로 선택. (가장 빨리 시작하면서 가장 빨리 끝나는 것)