1931_회의실배정 (JAVA)

1931번: 회의실배정

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

public class Main {
	static class Arr implements Comparable<Arr>{
		int start; int end;
		public Arr(int start, int end){
			this.start = start; this.end = end;
		}
		@Override
		public int compareTo(Arr arr){ //end기준으로 오름차순정렬
			if(this.end > arr.end)
				return 1;
			if(this.end == arr.end){ //start도 오름차순 정렬
				if(this.start > arr.start)
					return 1;
			}
			return -1;
		}
	}

	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int N = sc.nextInt();

		Arr[] arr = new Arr[N];
		for(int i=0; i<N; i++){
			int x = sc.nextInt();
			int y = sc.nextInt();
			arr[i] = new Arr(x, y);
		}

		Arrays.sort(arr);

		int ans = 0;
		int endpoint = -1; //시간 최소값=0 이므로 더 작은값으로 설정

		for(int i=0; i<N; i++){
			if(endpoint <= arr[i].start){
				endpoint = arr[i].end;
				ans++;
			}
		}
		System.out.println(ans);
	}
}

 

 

1. 회의실을 가장 많이 배정해야 하므로, 회의가 끝나는 시간과 시작하는 시간을 비교하며 카운팅해야한다.

 

2. 가장 먼저 시작하는 회의를 결정하는 것이 중요하다.

   '끝나는 시간'을 기준으로 정렬한다. ('시작하는 시간'도 오름차순으로 정렬해야 한다)

   왜냐면 - '끝나는 시간'이 작을 수록 '시작하는 시간'이 빨라지고, 회의실 배정을 더 많이 할 수 있기 때문!

 

3. 정렬이 된 배열을 0부터 탐색한다.

   끝나는 시간 <= 시작하는 시간 의 조건을 만족하면 ans++

 

 

 

회의가 끝나는 시간을 오름차순으로 정렬했을 때 - 첫 번째 원소, 즉 가장 빨리 끝나는 회의를

시작으로 회의실을 배정해야 한다고 잘못 생각해서 오래 걸렸다ㅠㅠ 내 맘대로 결정하지 말아야지..!