문제

회의실 배정

풀이

이 블로그를 참고하였다. 활동 선택 문제(activity selection problem) 라고 하는 문제라고 한다. 또는 interval scheduling. 서로 겹치지 않는 범위를 가진 최대 개수를 구한다. 회의실의 종료시간이 가장 작은 것들 중에도 종료시간에 가장 가까운 시작점을 가진 것을 선택해야 한다

1. 종료 시간을 기준으로 오름차순으로 정렬한다.

	static class Meeting implements Comparable<Meeting> {
        int start;
        int end;

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

        @Override
        public int compareTo(Meeting o) {
            if (this.end == o.end) {
                return this.start - o.start;
            }
            return this.end - o.end;
        }
    }

• 종료시간이 같은 경우에는 가장 시작 시간이 작은 순으로 정렬한다

2. 정렬 후 이전 종료 시점보다 큰 것이 다음 시작하게 될 회의 가 될 것이다.

		Collections.sort(arr);
        int count = 0;
        int prev_end = 0;
        for (int i = 0; i < n; i++) {
            if (arr.get(i).start >= prev_end) {
                prev_end = arr.get(i).end;
                count++;
            }
        }

전체 코드

전체 코드