[백준/1931][Java] 회의실 배정

문제

1931번: 회의실 배정

알고리즘

그리디

서로 겹치지 않는 회의에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다

끝나는 시간을 기준으로 오름차순 정렬을 진행한다. 이때 끝나는 시간이 동일하다면 시작 시작이 더 빠른 것이 앞쪽으로 오게된다.

 

코드1

package algo0317;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class B1931_회의실배정 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int[][] time = new int[n][2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			time[i][0] = Integer.parseInt(st.nextToken()); // 시작시간
			time[i][1] = Integer.parseInt(st.nextToken()); // 종료시간
		}

		// 끝나는 시간을 기준으로 정렬. 이때 종료 시간이 같으면 시작 시간을 기준으로 정렬
		Arrays.sort(time, new Comparator<int[]>() { // 정렬의 대상이 1차원 배열이다.
			@Override
			public int compare(int[] s, int[] e) {
				if (s[1] == e[1]) { //종료 시간이 같은 경우
					return s[0] - e[0]; //시작 시간을 기준으로 정렬한다.
				}
				return s[1] - e[1];
			}
		});
		int count = 0;
		int end = -1;
		for(int i = 0;i<n;i++) {
			if(time[i][0]>=end) {
				//직전 종료 시간이 다음 회의 시작 시간보다 작거나 같다면 갱신
				end = time[i][1];
				count++;
			}
		}
		System.out.println(count);
	}

}

코드2 - 배열이 아닌 클래스를 생성하여 문제 해결

package algo0317;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class B1931_회의실배정2 {
    public static int getSchedule(Meeting[] m) {

        Arrays.sort(m); // 회의 종료시간(오름) 순서대로 정렬
        int beforeEnd = m[0].end; // 첫번째 회의 확정
        int cnt = 1;
        for (int j = 1; j < m.length; j++) {
            // 확정된 앞 회의의 종료시간이 다음 회의시작보다 같거나 크다면 회의 확정
            if (beforeEnd <= m[j].start) {
                ++cnt;
                beforeEnd = m[j].end;
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine().trim());
        Meeting m[] = new Meeting[count];

        StringTokenizer st = null;
        for (int i = 0; i < count; i++) {
            st = new StringTokenizer(br.readLine());
            m[i] = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        System.out.println(getSchedule(m));
    }
    
    static class Meeting implements Comparable<Meeting> {
        int start;
        int 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){
            	return this.start-o.start;// 종료시간이 같을 경우 시작시간이 빠른 순으로 정렬되도록 한다.
            }
            return this.end-o.end;
        }
    }
   }