[추가] 회의실 배정 - 그리디 문제

🟦 회의실 배정 - 그리디 문제

회의실 배정 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

▣ 입력설명 첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

회의 시간은 0시부터 시작된다. 회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

▣ 출력설명 첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

---

💚나의 풀이 - 그리디

• “안겹치게” 하는 게 중요하다.
• 안겹치려면 앞 회의의 종료 시간과 뒷 회의의 시작 시간이 같거나 커야 하므로
• 종료시간 기준으로 정렬시킨 뒤, 현재 종료시간보다 크거나 같은 시작 시간 발견 시
• 1. cnt++ 2) 기준 시간을 다시 해당 회의실 종료 시간으로 갱신시킨다.

package to_0615_7;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/*회의실 배정 */
class Room implements Comparable<Room>{
	int st;
	int ed;
	Room(int st, int ed){
		this.st = st;
		this.ed =ed;
	}
	@Override
	public int compareTo(Room o) {
		// TODO Auto-generated method stub
		if(this.ed == o.ed) return this.st - o.st;
		return this.ed - o.ed;
	}
	
}
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		ArrayList<Room> arr = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			int a = kb.nextInt();
			int b= kb.nextInt();
			arr.add(new Room(a,b));
		}
		Collections.sort(arr);
		
		int cnt= 1;
		int pivot = arr.get(0).ed;
		
		for(int i=1; i<n; i++) {
			if(pivot <= arr.get(i).st) {
				cnt++;
				pivot = arr.get(i).ed;
			}
		}
		System.out.println(cnt);
	}
}