백준 -1931 회의실 배정

www.acmicpc.net/problem/1931

1931번: 회의실 배정

---

정렬 기준을 잡는다면 쉽게 해결할 수 있음.

회의의 시간시간과 끝나는 시간이 주어져 있음. -> 각 회의가 겹치지 않게 회의실을 사용하는 회의의 최대개수 찾기

(회의의 시작시간과 끝나는 시간이 같을수 있다)

 

회의의 종료시간을 오름차순으로 정렬 후 

다음 회의의 시작시간이 앞선 회의의 종료시간보다 크거나 같다면 list에 추가해주었다.

**주의** 만약 종료시간이 같은 회의가 존재한다면 시작시간이 앞선 회의를 먼저 list에 담아야 함 (시작시간 오름차순)

 

그리고 마지막에 list의 사이즈를 출력함으로써 배정된 회의의 수를 구하였다.

---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class 회의실 배정 {
	static class Meeting implements Comparable<Meeting>{//회의정보를 클래스를 만들어 관리
		int start,end;//회의 시작시간 종료시간

		public Meeting(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Meeting o) {
			if (this.end - o.end==0) {//만약 끝나는 시간이 같은 경우
				return o.start-this.start;//시작 시간을 오름차순
			}
			return this.end - o.end; //끝나는시간 순으로 오름차순
		}
		
	}
	static int N;
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/회의실.txt"));
		Scanner sc = new Scanner(System.in);
		ArrayList<Meeting> list = new ArrayList<Meeting>();
		N = sc.nextInt();//회의의 수
		Meeting []arr = new Meeting[N];
		for (int i = 0; i < N; i++) {
			arr[i] = new Meeting(sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(arr);//끝나는시간순으로 정렬
		list.add(arr[0]);//끝나는시간이 제일빠른회의 리스트에 먼저 삽입. 
		//비교시작
		for (int i = 1; i < N; i++) {
			//만약 리스트에들어간 회의종료시간보다 다음 회의시간이 같거나 크다면 넣는다.
			
			if(arr[i].start>=list.get(list.size()-1).end) {
				list.add(arr[i]);
			}		
		}
		System.out.println(list.size());//list의 사이즈= 들어간 회의의 수 
		
		
	}
	

}