[C++] 백준 1931: 회의실 배정

[C++] 백준 1931: 회의실 배정

🥈 실버 1

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

1931번: 회의실 배정

---

 

접근

 

이미 진행중인 회의가 있다면, 다음  회의로 현재 회의가 끝나는 시간과 가장 가까운 회의가 선택되어야 최댓값을 가질 수 있다.

반복문을 한번만 돌려서 이를 효과적으로 구현하기 위해서는 입력된 값을 어떤 기준을 삼아 정렬시킬 필요가 있다.

위의 예제 입력 케이스를 참고하여 x축을 회의 시간으로 해서 나타내면 아래와 같다.

예제에서 입력 값들을 어떻게 정렬해야 할지에 대한 힌트를 주고 있었다.

회의가 끝나는 시간을 기준으로 입력받은 pair의 값을 정렬하면 된다.

 

회의가 가능한 시간대를 표시하면 다음과 같았다.

노란 부분만 추려낼 수 있는 간단한 방법이 있었다.

 

1---4를 기준으로 살펴보자.

회의가 끝나는 시간은 4시이다.

다음 요소인 3---5와 0----6에 회의를 시작하지 못하는 이유는

4시보다 더 빨리 회의가 시작되어 회의 시간대가 겹치기 때문이다.

 

따라서 4시 이후에(4시 포함) 회의가 시작되는 요소인 5----7에 다음 회의를 진행할 수 있다.

 

구현을 위한 포인트를 정리하면 다음과 같다.

 

1. pair vector를 만들고 maik_pair를 통해 한 쌍씩 벡터에 넣어준다.

2. 두번째 값을 기준으로 오름차순 정렬하되, 두번째 값이 같은 경우에는 첫번째 값을 기준으로 오름차순 정렬한다.
(입력케이스가 3 5, 2 5가 들어올 경우, 2 5, 3 5 순으로 배치되어야 하기 때문이다.)

3. 현재 진행중인 회의가 끝나는 시간 이후로 가장 빨리 시작되는 회의를 고르고 count를 올린다. (이미 회의 하나가 시작되었음을 전제로 하기 때문에 최초 count 변수의 값은 1이 되어야 한다.

 

코드

 

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

bool sortBySecond(const pair<int, int>&a, const pair<int, int>&b ) {
  if (a.second != b.second) {
    return a.second < b.second;
  }
  else {
    return a.first < b.first;
  }
}

int main() {
  vector<pair<int, int>> vec;

  int N;
  cin >> N;

  while(N--) {
    int a, b;
    cin >> a >> b;
    vec.push_back(make_pair(a, b));
  }
  
  sort(vec.begin(), vec.end(), sortBySecond);

  int cnt = 1;
  int curIdx = 0;
  for (int i = 1; i < vec.size(); i++) {
    if (vec[curIdx].second <= vec[i].first) {	// 현재 진행중인 회의를 기준으로 다른 회의들을 비교한다.
      curIdx = i;
      cnt++;
    }
  }
  cout << cnt;
  return 0;
}