[2021 ICT 하반기] 4번 문제

요약: 시작시간과 끝나는 시간이 주어지는 N개의 회의가 있을 때 하나의 회의실에 최대로 많이 넣을 수 있는 회의의 개수를 구하는 문제입니다. 

 

설명: 일찍 끝나는 회의 순으로 정렬한 후, 순서대로 회의실이 비어있으면 회의를 집어넣으면 됩니다. 끝나는 시간을 기준으로 했던 이유를 보여주는 예시) 1~10시 까지 회의, 2~4시 까지의 회의, 4~5시 까지의 회의 가 있으면 1~10시까지의 회의 보다 나머지 두 개의 회의를 넣는게 더 이득이다.

 

#include <bits/stdc++.h> // 모든 표준 라이브러리 헤더들을 가져오는 전처리문
using namespace std; // std라는 namespace에서 사용하려고 한다. 그냥 암기하면 됨

// 구조체 Time 선언
struct Time {
   int start_time;
   int end_time;
};

/*
   정렬의 기준을 정의한다. (사용자 정의로 customizing해서 쓸 수 있음)
   임의의 두 Time 구조체끼리 비교할 때, 
      swap을 해서 위치를 바꿀 건지(false, 즉 현재 조건을 만족하지 않음), 그대로 둘건지(true, 현재 조건을 만족함)를 리턴한다.
*/
bool compare(Time t1, Time t2) { 
   if (t1.end_time == t2.end_time) { // t1의 종료 시간(end_time)과 t2의 종료 시간(end_time)이 같다면. 
      return t1.start_time < t2.start_time; // t1의 시작 시간(start_time) < t2의 시작 시간(start_time) 조건의 결과값(true 또는 false)을 리턴한다. (즉, 오름차순으로 정렬하게 된다.)
   }
   // 그렇지 않은 경우(즉, t1과 t2의 종료 시간이 다른 경우)
   return t1.end_time < t2.end_time; // t1의 종료시간 < t2의 종료시간 조건을 리턴한다. (즉, 오름차순으로 정렬하게 됨)
}

/*
   문제:
      n개의 회의가 주어지고, 각 회의는 시작 시간과 지속 시간이 있다. (당연히 종료시간=시작시간+지속시간이다.)
      회의실이 1개일 때, 최대한 많은 회의를 커버하고 싶다. 이 때 최대 회의 수는?

   솔루션:
      일찍 끝나는 회의 순으로 정렬한 후, 순서대로 sweeping하면서 선택한다.
      (구글에 "회의실 문제" 또는 "회의실 배정 문제"로 검색하면, 자세한 설명들이 있다.)
      (참고로, 이 문제는 욕심쟁이 기법(greedy) 알고리즘의 가장 대표적인 문제이다.)
*/
int maxEvents(vector<int> arrival, vector<int> duration) {
   int n = arrival.size(); // 회의 갯수를 n에 저장

   /*
      각 element의 타입이 구조체 Time인 벡터 times를 선언. 크기는 n
      구조체 Time을 선언해서 새로운 벡터를 만드는 이유:
         원래 문제에서는 시작 시간 arrival, 지속 시간 duration가 매개변수로 주어지는데, 
         구조체로 묶어서 (시작 시간, 종료 시간) 형태로 바꿔서 저장하면, sort할 때 편하다.
   */
   vector<Time> times(n);
   for (int i=0; i<n; i++) { // n개를 훑으면서
      times[i].start_time = arrival[i]; // 시작 시간은 그대로..
      times[i].end_time = arrival[i] + duration[i]; // 당연히 종료 시간 = 시작 시간 + 지속 시간이다.
   }

   /*
      times 벡터를 정렬한다. 정렬 기준은 compare 함수이다.
      종료 시간(end_time) 순으로 정렬하되, 종료 시간(end_time)이 같은 경우엔 시작 시간(start_time)이 빠른 놈으로 한다. 
         근데 사실 시작 시간 순으로 sort안해도 된다. 시작 시간은 아무렇게나해도 됨. 잘 생각해보면됨
   */
   sort(times.begin(), times.end(), compare);

   int last_finished_time = 0; // 마지막 회의 종료 시간 (시작 전에는 time = 0. 모든 start_time은 1 이상이니까 처음엔 0으로 두면 됨)
   int result = 0; // 선택한 회의 갯수. (시작 전에는 당연히 0개)
   for (int i=0; i<n; i++) { // 정렬된 회의들을 순서대로 sweeping하면서(훑으면서)

      // 마지막 회의 종료 시간이 i번째 회의의 시작시간(start_time) 이하인 경우 (즉, 회의실이 비어서 현재 회의가 들어갈 수 있는 경우)
      if (last_finished_time <= times[i].start_time) { 
         last_finished_time = times[i].end_time; // last_finished_time을 i번째 회의의 종료시간(end_time)으로 갱신해버린다. (즉, 회의를 추가해서 시작하고 끝났음)
         ++result; // i번째 회의를 선택했으므로 result에 +1
      }
   }
   return result; // 결과값 result를 리턴
}

int main()
{
   // 입력하는 부분 생략하고, 바로 변수에 저장
   int n = 3; // arrival[] size n = 3
   vector<int> arrival = { 1, 3, 5 }; // arrival = [1, 3, 5]
   vector<int> duration = { 2, 2, 2 }; // duration = [2, 2, 2]
   
   // maxEvents 함수 호출하고 결과값 저장
   int answer = maxEvents(arrival, duration);
   
   // 결과값 출력
   cout << answer;

   return 0; //정상 종료됨을 의미하는 return 0
}

 

주석 제거용

#include <bits/stdc++.h>
using namespace std; 

struct Time {
   int start_time;
   int end_time;
};

bool compare(Time t1, Time t2) { 
   if (t1.end_time == t2.end_time) {
      return t1.start_time < t2.start_time; 
   }
   return t1.end_time < t2.end_time;
} //끝나는 시간을 기준으로 정렬하기 위해 compare 함수를 만들었습니다. 

int maxEvents(vector<int> arrival, vector<int> duration) {
   int n = arrival.size();

   vector<Time> times(n);
   for (int i=0; i<n; i++) { 
      times[i].start_time = arrival[i];
      times[i].end_time = arrival[i] + duration[i]; 
   }

   sort(times.begin(), times.end(), compare);

   int last_finished_time = 0; 
   int result = 0; 
   for (int i=0; i<n; i++) {

      if (last_finished_time <= times[i].start_time) { 
         last_finished_time = times[i].end_time; 
         ++result; 
      }
   }
   return result;
}

int main()
{
   int n = 3; 
   vector<int> arrival = { 1, 3, 5 }; 
   vector<int> duration = { 2, 2, 2 }; 
   
   int answer = maxEvents(arrival, duration);
   
   cout << answer;

   return 0; 
}