[알고리즘] - BOJ #1931 회의실 배정

• 이번 문제는 BOJ #1931, 회의실 배정입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

접근 방식

1. 처음에는 지속 시간을 기준으로 가장 작은 것들부터 회의실을 배치하는 방식으로 문제에 접근했습니다.

• 그 결과, 테스트 케이스로 주어진 입력과 여러 다른 케이스의 경우 올바른 답을 구해냈지만, 아래와 같은 반례가 존재했습니다.

  1 5
  4 6
  5 8
  7 9
  8 10
  ---
  output : 2
  answer : 3
  

• 이 경우, 문제의 요구 조건에 따르면 (1,5), (5,8), (8,10) 이 세 가지를 조합하여 최대 3개의 회의를 진행할 수 있습니다.
• 그러나 1번의 접근 방식으로 시도할 경우, 지속 시간이 짧은 (4,6), (7,9)를 먼저 배치하게 되고, 나머지 회의는 해당 회의들과 겹치는 시간이 존재하여 배치될 수 없기 때문에 최대 회의 진행 수가 2로 출력되는 문제가 발생했습니다.
  
  

2. 끝나는 시간을 기준으로 가장 작은 것들을 우선적으로 배치하는 방식으로 접근했습니다.

• 그 결과, 위의 반례에 대해서도 올바른 정답을 출력하는 것을 확인할 수 있었습니다.
• 그러나 끝나는 시간이 동일한 회의들에 대해서 정렬 기준을 세우지 않다보니, 아래와 같은 반례가 존재했습니다.

  3
  3 3
  1 3
  4 5
  ---
  output : 2
  answer : 3
  

• 이 경우, (3,3)과 (1,3)의 경우 끝나는 시간이 동일하기 때문에 정렬 기준을 단순히 끝나는 시간으로만 설정할 경우 시스템 상에서 입력에 의해 (3,3)이 (1,3)보다 앞서 위치하게 됩니다. (오름차순 정렬 기준)
• 이에 따라 (3,3)을 우선 배치 한 뒤, (3,3)과 (1,3)을 비교하게 되는데 제가 구현한 로직에서는 새로 들어온 (1,3)의 시작 시간과 기존에 존재하고 있던 (3,3)의 종료 시간을 비교하게 되기 때문에 (1,3)을 배치할 수 없게 되었습니다.

• 이 때문에, 제가 구현한 로직상에서 정상적으로 답을 출력하기 위해서는 시스템의 입력 순서와 상관 없이 (1,3)을 (3,3)보다 먼저 정렬되도록 해야했습니다.

• 이를 위해, 종료 시간이 동일할 경우 시작 시간을 두 번째 정렬 기준으로 사용하도록 했습니다.

  // Endtime기준 정렬
  Arrays.sort(meetArr, new Comparator<int[]>() {
      @Override
      public int compare(int[] i1, int[] i2) {
          // Endtime 기준 오름차순 정렬
          // Endtime이 동일하다면 Starttime 기준 오름차순 정렬
          return i1[1] == i2[1] ? i1[0] - i2[0] : i1[1] - i2[1];
      }
  });
  

• 그 결과 위의 반례에 대해서도 정상적으로 동작하는 것을 확인할 수 있었습니다.
  
  

알고리즘 분류

• 회의실 배정 문제는 그리디 알고리즘으로 분류됩니다.
• 종료 시간을 기준으로 가장 작은 것을 우선 배치하는 행위가 그 뒤의 나머지 회의를 배치하는데 있어 영향을 미치지 않습니다.
  • ‘가능한 최대의 회의 수를 구한다’는 문제의 상황 아래에서 영향을 미치지 않습니다.
• 따라서, 문제를 푸는 과정에서 종료 시간을 기준으로 오름차순 정렬을 한 뒤, 종료 시간이 작은 것들을 우선적으로 배치하는 방식으로 문제를 해결할 수 있습니다.

문제 바로가기 👉 BOJ #1931