[BOJ] 1931_회의실 배정

회의실 배정

문제 링크: https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

회의 시간을 모두 입력받고 정렬이 필요하다.
그 기준은 회의 시간의 시작과 끝인데, 회의 종료 시간이 빠르면 빠를수록 그 뒤에 오는 회의가 더 많아질 수 있다.
시작이 빠르다고 회의가 빨리 끝나는 것이 아니므로 정렬 기준은 회의 종료시간이라 할 수 있다.
그리고 회의의 수를 카운트하면 되는데, 회의가 진행하고 있는 중에 새로운 회의가 들어오면 안되므로 하나의 회의가 종료하기 전에 새 회의의 시작시간이 들어온다면 새 회의는 불가능 하다.
그래서 종료시간과 새 회의시간의 시작시간을 비교해서 종료시간보다 시작시간이 더 클 경우 카운트 해준다.

 

정렬하는데 있어 고려해야할 점이 있다.
회의 진행시간이 짧은 것이 더 많은 회의가 들어간다는 것이다.
회의 종료시점을 비교하는데 같은 시간대에 종료한다면, 회의 진행시간이 더 짧은 것이 더 많은 회의를 진행시킬 수 있다는 것이다.
회의 진행시간이 더 짧다는 것은 시작시간과 종료시간 간격이 더 짧다는 의미이며, 시작시간을 비교했을 때 더 늦게 시작한다는 뜻이다.

• 정답 코드

    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
  
    bool compare(pair<int, int>* arr1, pair<int, int>* arr2) {
        if(arr1->second == arr2->second)
            return arr1->first < arr2->first;
        return arr1->second < arr2->second;
    }
  
    int main() {
        int n;
        cin >> n;
        vector<pair<int,int>*> list;
        while (n--) {
            pair<int, int>* pa = new pair<int, int>;
            cin >> pa->first >> pa->second;
            list.push_back(pa);
        }
        sort(list.begin(), list.end(),compare);
  
        int Count = 0;
        pair<int, int>* preList = list[0];
        Count++;
        for (int i = 1; i < list.size(); i++) {
            if (preList->second <= list[i]->first) {
                Count++;
                preList = list[i];
            }
        }
  
        cout << Count << endl;
        return 0;
    }