C++ - 백준 1931번. 회의실배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다

 

해결 알고리즘 : 그리디 알고리즘

---

그리디 알고리즘이란?

지금 순간에 가장 최선의 선택이라고 생각하는 선택을 하는 것.

 

이 문제에 그리디 알고리즘을 적용하기 위해서 아래의 두 가지 조건을 만족해야 한다.

 

조건 1. 

회의의 시작 시간이 이미 기준점으로 선택된 회의의 끝나는 시간과 같거나 늦어야 한다.

 

조건2.

가장 빨리 끝나는 회의를 선택해야 한다.

--> 회의의 끝나는 시간을 기준으로 오름차순으로 정렬되어 있어야 한다.

C++에서는 algorithm library를 include해주면 따로 구현하지 않아도 sorting을 사용할 수 있다.

우리는 struct Time의 F (finish time) 변수를 기준으로 sorting을 해준다.

여기서 주의할 점은, 만약 두 회의의 마치는 시간이 동일하다면 시작 시간이 더 빠른 회의를 먼저 위치하도록 해줘야 한다.

compare 함수를 구현하여 sorting을 해줬다.

 

* 시작 시간과 마치는 시간의 input값이  2^31-1 까지의 범위이기 때문에, long long 타입을 사용해야 한다.

#include <iostream>
#include <algorithm>
using namespace std;

// 회의실 배정 - 그리디 알고리즘 
struct Time{
  long long S;
  long long F;
};

bool compare (Time &t1, Time &t2) {
  if(t1.F == t2.F)  return t1.S < t2.S;
  else  return t1.F < t2.F;
}

int main() {

  int N;
  cin >> N;
  struct Time time[N];
  int maximum=0;

  for(int i=0 ; i < N ; i++ ) {
    cin >> time[i].S >> time[i].F;
  }
  
  sort( time, time+N, compare );

  // 기준이 되는 애들의 시간.
  long long start=0, finish=0;

  for(int i=0 ; i < N ; i++ ) {
    // 1번 조건. start 시간이 앞 회의의 finish 시간보다 같거나 늦어야 하고,
    // 2번 조건. finish 시간이 제일 빠른 회의를 골라야 함.
    if(time[i].S >= finish) {
      start = time[i].S;
      finish = time[i].F;
      maximum++;
    }
    else  continue;
  }
  cout << maximum << endl;
}

sorting 하는데 nlogn의 time complexity가 걸리고, 회의의 최대 개수를 구하는데는 linear한 시간이 소요되기 때문에

이 문제의 time complexity는 nlogn임을 알 수 있다.