회의실배정 (Greedy)

회의 시작 시간과 종료 시간이 주어졌을 때, 최대 회의수 구하는 문제

 

정답 : 

1.

회의가 끝나는 시간을 기준으로 오름차순 정렬한다.

만약 종료되는 시간이 같다면, 시작시간을 기준으로 오름차순 정렬

 

2.

회의시간이 빨리 끝나는 순서대로 겹치지 않도록 카운트 한다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer;

	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();

		ArrayList<Schedule> ar = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			ar.add(M.new Schedule(in.nextInt(), in.nextInt()));
		}

		Collections.sort(ar);
		int cnt = 0;
		int prevEndTime = 0;
		for (Schedule sc : ar) {
			//System.out.println(String.format("%d %d", sc.s,sc.e));
			int start = sc.s;
			int end = sc.e;

			if (prevEndTime <= start) {
				prevEndTime = end;
				cnt++;
			}
		}

		System.out.println(cnt);

	}

	class Schedule implements Comparable<Schedule> {
		int s, e;

		Schedule(int s, int e) {
			this.s = s;
			this.e = e;
		}

		@Override
		public int compareTo(Schedule o) {
			if( this.e == o.e)
				return this.s - o.s;
			return this.e - o.e;
		}
	}

}
ex)
5
5
1 4
2 3
3 5
4 6
5 7
output
3

ex)
input
3
3 3
1 3
2 3
output
2