<8주차> [BOJ / C++] 1931번 - 회의실 배정

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

1931번: 회의실 배정

 

 

 

문제

 

 

코드

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

pair<int, int> s[100005];

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


int main(void)
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for (int i=0; i<n; i++)
  {
    cin >> s[i].first >> s[i].second;
  }
  sort(s, s+n, cmp);
  int ans=0;
  int t=0; //현재시간으로 0으로 초기화
  for (int i=0; i<n; i++)
  {
    if (t > s[i].first) //각 회의가 겹치면 안 됨
      continue;
    ans++;
    t = s[i].second;
  }

  cout << ans;
}

 

 

풀이

그리디로 해결했다.

pair에서 first = 시작시간 / second = 종료시간이다.

원하는 기준으로 정렬하기 위해 sort에 cmp함수를 인자로 준다.

cmp함수는 종료시간이 빠른게 앞에 오도록 하고, 만약 종료시간이 서로 같다면 시작시간이 빠른게 앞에 오도록 한다.

종료시간이 같을 때 시작시간이 빠른게 앞에 와야하는 이유는 정렬된 것들을 앞에서 부터 확인하여 조건을 따져가며 ans를 증가시킬건데 예를들어 (6,8), (10,10), (8,10) 과 (6,8), (8,10), (10,10)의 경우를 비교해보면 전자는 ans가 2증가하는데에 반해 후자는 ans가 3증가한다. 결과적으로 시작시간과 종료시간이 같은 경우 때문에 종료시간이 같을 때, 시작시간이 빠른게 앞에 와야하는 것이다.

 

 

결과