[Java] 백준 1931 회의실 배정 - 실버1

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    //입력받기 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
    StringTokenizer st = new StringTokenizer(br.readLine());
    int cnt = Integer.parseInt(st.nextToken());

    int[][] time = new int[cnt][2];
    for (int i=0; i<cnt; i++) {
      st = new StringTokenizer(br.readLine());
      time[i] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
    }
    //입력끝 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

    Arrays.sort(time, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        if(o1[1] != o2[1])
          return o1[1] - o2[1];

        return o1[0] - o2[0];
      }
    });

    int result = 0;
    int finishTime = 0;

    for (int i =0; i<cnt; i++) {
      if (time[i][0] >= finishTime) {
        finishTime = time[i][1];
        result ++;
      }
    }

    System.out.println(result);
  }
}

• 종료값을 기준으로 정렬하고, 같은 값일 경우 시작 값을 기준으로 정렬을 한다
• 종료시간이 가장 빠른 것을 우선적으로 고르고, 이전에 일을 끝낸 시간과 시작시간이 가장 가까운 값을 고르게 된다

 

 

알고리즘 수업시간에 배워서 쉽게 풀 수 있었다.

그리디 문제로 풀 수 있는 스케줄링 문제(가장 많은 회의 수)는 종료시간이 가장 빠른 것을 우선적으로 뽑으면 최선의 값을 얻을 수 있다.