섹션 9 Greedy - 2. 회의실 배정

문제 설명

한 회의실에서 여러 회의를 하려고 한다.
각 회의는 시작시간과 종료시간이 주어지고,
겹치지 않게 최대한 많은 회의를 배정하려고 한다.

• 단, 끝나는 시간과 동시에 다음 회의 시작 가능
• 중간 중단 불가

---

입력 & 출력

입력

5
1 4
2 3
3 5
4 6
5 7

 

출력

3

---

해결 방법

• 빨리 끝나는 회의를 우선 배정하면 다음 회의에 더 많은 기회 확보 가능
• 따라서 종료 시간 기준으로 오름차순 정렬
• 종료 시간이 같다면 시작 시간이 빠른 순으로 정렬
• 각 회의마다 직전 회의의 종료 시간 이후에 시작하면 배정

---

코드 구현

import java.util.*;

class Meeting implements Comparable<Meeting> {
	int start, end;
	Meeting(int start, int end) {
		this.start = start;
		this.end = end;
	}
	@Override
	public int compareTo(Meeting o) {
		if (this.end == o.end) return this.start - o.start;
		return this.end - o.end;
	}
}

public class Problem2 {
	public int solution(ArrayList<Meeting> arr) {
		Collections.sort(arr);
		int answer = 0, last = 0;
		for (Meeting m : arr) {
			if (last <= m.start) {
				answer++;
				last = m.end;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Problem2 T = new Problem2();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<Meeting> arr = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			arr.add(new Meeting(start, end));
		}
		System.out.print(T.solution(arr));
		sc.close();
	}
}

---

코드 설명

• Meeting: 회의 시작/종료 정보를 담은 클래스
• compareTo: 종료 시간 기준 정렬, 같으면 시작 시간 기준
• solution():
  • 회의를 정렬 후, 이전 회의 종료 시각 last를 기준으로 배정 여부 결정
  • if (last <= m.start) → 회의 배정, 종료 시간 갱신

---

시간 복잡도

• 정렬: O(N log N)
• 순회: O(N)
• 전체 시간 복잡도: O(N log N)

N ≤ 100,000이므로 정렬 기반 풀이가 최적이다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런