[백준] 1931번 회의실 배정

문제

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

입력

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

출력

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

 

이 문제는 어떤 것을 정렬하는지가 더 중요한 문제라 생각이 든다.

처음에는 시작 시간을 기준으로 정렬을 하였다.

시작 시간을 정렬해도 문제를 풀 수 는 있지만, 이중 배열을 사용해야하기 때문에 시간 초과가 발생한다.

그러면 어떻게 해야할까?

바로 시작 시간이 아니라 끝나는 시간을 기준으로 정렬을 해야한다.

끝나는 시간으로 정렬을 할 경우,

자연스럽게 그 시간보다 작은 시간들을 모조리 무시하면 된다.

11

1 4

3 5

0 6

5 7

3 8

5 9

6 10

8 11

8 12

2 13

12 14

이런 예제가 있다고 가정하자.

이 예제에서는 끝나는 시간이 정렬이 되어있다.

그러면 첫 번째 꺼만 확인해보면

시작시간이 4보다 같거나 큰 숫자가 나올때 숫자를 바꿔주면 된다.

즉, 위로 확인해보면 4보다 큰 숫자는 5가 되기 때문에

1, 4 -> 5,7 -> 8,11 -> 12,14가 최종 결과가 되며

정답은 4로 나온다.

이것을 코드로 작성해보면

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

int main(void) {   
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  int n;
  cin >> n;

  pair<int,int> arr[n];

  for(int i = 0; i<n;i++) {
    cin >> arr[i].second >> arr[i].first;
  }

  sort(arr,arr+n);

  int cnt = 1;
  int time = arr[0].first;
  // cout << arr[0].second << " " << 
  // arr[0].first << "\n";

  for(int i = 1; i<n;i++) {
    if (time <= arr[i].second) {
      time = arr[i].first;
      // cout << arr[i].second << " " << 
      // arr[i].first << "\n"; 
      cnt++;
    }
  }

  cout << cnt << "\n";

}

 

c++은 first를 기준으로 정렬하기 때문에 일부로 first를 끝나는 시간으로 설정해두었다.