백준1931_회의실 배정

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

 

 

여러 시간대가 주어지고, 시간이 겹치지 않으면서 가능한 한 많은 회의실 사용 횟수를 구하려고 한다.

 

이를 구하기 위해서는, 가장 빨리 끝나는 회의를 찾고,

 

그 이후에 시작하는 회의 중 가장 빨리 끝나는 회의를 찾고,

 

이렇게 찾아나가면 될 것 같다.

 

위와 같이 회의 시간을 찾기 위해서는, 끝나는 시간을 기준으로 정렬되어 있어야 한다.

 

 

이를 위해 다음과 같은 구조체와 배열을 만들어 주고,

이렇게 끝나는 시간을 기준으로 정렬해주는 cmp함수까지 완성해주면 준비는 끝났다.

(끝나는 시간이 같은 경우 시작 시간을 기준으로 정렬)

bool cmp(const t& a, const t& b) {
  if (a.eTime != b.eTime) return a.eTime < b.eTime;

  return a.sTime < b.sTime;
}

 

 

정렬이 완료되었다면, 배열의 처음부터 끝까지 돌며

가능한 회의의 개수를 세어주면 된다.

int count = 0;
  int end = 0;

  for (int i = 0; i < N; i++) {
    if (v[i].sTime >= end) {
      count++;
      end = v[i].eTime;
    }
  }

  std::cout << count << '\n';

 

 

전체 코드

#include <algorithm>
#include <iostream>
#include <vector>

struct t {
  int sTime;
  int eTime;
};

bool cmp(const t& a, const t& b) {
  if (a.eTime != b.eTime) return a.eTime < b.eTime;

  return a.sTime < b.sTime;
}

int main(void) {
  std::ios::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cout.tie(NULL);

  int N;
  std::cin >> N;

  std::vector<t> v(N, {0, 0});

  for (int i = 0; i < N; i++) {
    std::cin >> v[i].sTime >> v[i].eTime;
  }

  std::sort(v.begin(), v.end(), cmp);

  int count = 0;
  int end = 0;

  for (int i = 0; i < N; i++) {
    if (v[i].sTime >= end) {
      count++;
      end = v[i].eTime;
    }
  }

  std::cout << count << '\n';

  return 0;
}