[BOJ] 1931: 회의실 배정

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

BOJ - 회의실 배정

문제 유형: 정렬, 그리디

문제 난이도: Silver I

시간 제한: 2초

메모리 제한: 128MB

 

 

문제

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

 

입력

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

 

출력

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

 

풀이

한 방이 최대한 많은 회의들을 가지려면, 각각의 회의가 최대한 일찍 끝나야 한다.즉, {회의시작, 회의종료}를 담은 배열에서 회의종료시간을 기준으로 오름차순 정렬한다.그러고 순차적으로 종료시간을 업데이트하면서 최대한 많은 회의를 가져가면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

struct comp {
  bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
    if (a.second == b.second)
      return a.first < b.first;
    return a.second < b.second;
  }
};

int n;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;

  int left, right;
  vector<pair<int, int>> meetings(n);
  for (int i = 0; i < n; ++i) {
    cin >> left >> right;
    meetings[i] = {left, right};
  }
  sort(meetings.begin(), meetings.end(), comp());

  int endTime = 0;
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (endTime <= meetings[i].first) {
      endTime = meetings[i].second;
      ans++;
    }
  }

  cout << ans << "\n";

  return 0;
}