[백준/자바] 1931번: 회의실 배정

문제

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

풀이

• 한 개의 회의실이 있는데, 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만드려고 한다.
• 각 회의에 대해 시작 시간과 끝나는 시간이 주어져 있다.
• 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 출력
  • 한 회의가 끝나는 동시에 다음 회의가 시작될 수도 있다.
  • 회의 시작 시간과 끝나는 시간이 같을 수도 있다.

그리디 문제입니다.
주어진 시간 안에 가장 많은 회의를 선택하는 문제죠

예전에 풀었던 문제라, 아이디어를 떠올리긴 쉬웠습니다.
더 자세한 풀이는 다음 링크를 참조해 주세요. [백준/파이썬] 1931번: 회의실 배정

---

끝나는 시간이 가장 빠른 회의부터 선택하면, 남은 시간대가 최대화되어 이후에 더 많은 회의를 배치할 수 있습니다.

만약 끝나는 시간이 같다면, 시작 시간이 빠른 것부터 선택하여 회의 시간이 0인 회의도 넣을 수 있게 됩니다.

코드

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

public class Main_1931 {
	
    // 회의 시간을 관리하는 클래스
	static class Time implements Comparable<Time> {
		int start, end;
		
		Time(int start, int end) {
			this.start = start;
			this.end = end;
		}
		
		@Override
		public int compareTo(Time o) {
        	// 끝나는 시간이 같다면, 시작 시간 순으로 정렬
			if (this.end == o.end) return Integer.compare(this.start, o.start);
            // 끝나는 시간이 다르다면, 끝나는 시간 순으로 정렬
			return Integer.compare(this.end, o.end);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 회의의 수
		
		Time[] times = new Time[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			times[i] = new Time(s, e); // (시작 시간, 종료 시간)
		}
		
		Arrays.sort(times); // 정렬
		
		int answer = 0, nxtStart = 0; // 정답, 다음 회의의 시작 시간
		for (Time t : times) {
			if (t.start >= nxtStart) { // 현재 회의의 시작 시간이 다음 회의 시작 시간과 같거나 늦은 시간이면
				answer++; // 정답++
				nxtStart = t.end; // 다음 회의 시작 시간 업데이트
			}
		}
		System.out.println(answer);
	}

}