백준 1931번: 회의실 배정

문제 설명

• 회의를 가장 많이 진행하는 방법을 찾는 문제입니다.

접근법

• 일반적인 그리디 문제입니다.

• 회의종료시간으로 정렬한 뒤 현재.종료시간<다음.시작시간일때마다 회의 개수를 1 늘립니다.

• 자세한 설명은 여기를 읽어주세요.

• 이 문제는 LinkedList로 값을 담으면 시간초과가 발생합니다.

  • 배열 혹은 ArrayList를 사용해 풀어야 합니다.
    • 배열과 ArrayList의 검색(.get)시간과 입력(.add)시간은 O(1)입니다.
    • LinkedList의 검색(.get)시간은 O(n)이기 때문입니다.

정답

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

public class Main {
	static int N;
	static class conference implements Comparable<conference>{
		int start,end;

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


		@Override
		public int compareTo(conference o) {
			return (this.end!=o.end)?this.end-o.end:this.start-o.start;
		}
		
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		conference[] arr = new conference[N]; //array를 쓰지 않고 list를 사용하면 시간초과가 납니다.
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			arr[i] = new conference(start,end);
		}
		Arrays.sort(arr);
		int answer = 0;
		int NowEnd = 0;
		for (int i = 0; i < N; i++) {
        	//시작시간과 끝나는 시간이 같은 회의가 있을 수 있기 때문에 '같다'가 들어갑니다.
			if(NowEnd<=arr[i].start) { 
				answer++;
				NowEnd = arr[i].end;
			}
		}
		
		System.out.println(answer);
	}
}