[Algorithm]알고리즘 자바_68 회의실 배정

💬 문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.

각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고,
각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

 

🔨 입출력 예

- 입력 

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

5
1 4
2 3
3 5
4 6
5 7

 

- 출력

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

 

3

 

 

💻 Solution.java

1. 먼저 끝나는 순을 기준으로 정렬한다.
2. 가장 빨리 끝나는 회의를 기준으로, 다음 회의는 끝나는 시간보다 크거나 같은 회의를 선택한다.
3. 만약 끝나는 순서가 같은 회의가 있으면, 시작하는 순서를 기준으로 회의를 정렬한다.

/* 회의실 배정 :: 그리디 알고리 */

import java.util.*;
class Time implements Comparable<Time>{
	public int s, e;
	Time(int s, int e){
		this.s = s;
		this.e = e;
	}
	
	@Override
	public int compareTo(Time o) { //object가 더 크면 음수 리턴, this가 더 크면 양수 리턴, 같은 값은 0 리턴
		if(this.e == o.e) return this.s - o.s;
		else return this.e - o.e;
	}
}

public class Main {
	
	public int solution(ArrayList<Time> arr, int n) {
		int cnt = 0;
		
		Collections.sort(arr);
		int et = 0;
		for(Time ob : arr) {
			if(ob.s >= et) {
				cnt++;
				et=ob.e;
			}
		}
		return cnt;
 	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		ArrayList<Time> arr = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			arr.add(new Time(x, y));
		}
		
		System.out.println(main.solution(arr, n));
		
		sc.close();
		return ;
	}
}