백준 1931번, 회의실 배정

백준 1931번 c++ 문제풀이

문제:

백준 1931

풀이:

1. 일단 이차원 벡터(v)로 회의실 시간을 저장 받는다.
2. 저장 받은 회의실 정보를 끝나는 시간(v[][1])을 기준으로 내림차순으로 정렬한다(벡터로 저장했기에).
3. 위 기준에 따라 끝나는 시간이 젤 빠른게 맨 뒤에 저장되므로 맨뒤에 것을 다른 이차원 벡터(v2)에 저장하고 v벡터는 pop_back한다.
4. v2벡터에 최근에 저장된 끝나는 시간 정보와 v벡터에 저장된 회의 시작 정보를 차례대로 비교 후,
   v벡터의 회의 시작 시간이 비교하는 끝나는 시간보다 더 크거나 같다면 그 값을 다시 v2에 저장한다.
5. 4번 과정을 반복한다.

이 문제는 끝나는 시간만 고려하면 되어서 greedy알고리즘을 사용했다.
이전 회의 끝나는 시간과 다음 회의 시작 시간을 비교하고 이 조건을 만족한다면 그 중 일찍 끝나는 회의를 고르면 되는 문제이다.

코드:

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

using namespace std;

bool cmp(vector<int> &v1, vector<int> &v2){ //끝나는 시간을 기준으로 정렬
    if(v1[1] == v2[1])
        return v1[0]>v2[0];
    else return v1[1]>v2[1];
}

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

    int n;
    vector<vector<int>> v;

    cin >> n;

    for(int i=0;i<n;i++){
        int start, end;
        vector<int> v1;
        cin >> start >> end;

        v1.push_back(start);
        v1.push_back(end);

        v.push_back(v1);
    }
    
    sort(v.begin(), v.end(), cmp);

    vector<vector<int>> v2;

    while(!v.empty()){
        if(v.size() == n){
            vector<int> v3;
            v3.push_back(v[v.size()-1][0]);
            v3.push_back(v[v.size()-1][1]);
            v2.push_back(v3);
            v.pop_back();
        }
        else{
            for(int i=v.size()-1;i>=0;i--){
                if(v[i][0] >= v2[v2.size()-1][1]){
                    vector<int> v4;
                    v4.push_back(v[v.size()-1][0]);
                    v4.push_back(v[v.size()-1][1]);
                    v2.push_back(v4);
                    v.pop_back();
                }else{
                    v.pop_back();
                }
            }
        }
    }
    
    cout << v2.size();
    return 0;
}

벡터를 이용해서 푸느라 코드가 더 복잡해진것 같다. 벡터를 무조건 사용하기 보단 더 간단하게 풀 수 있는 방법을 찾을 수 있으면 좋겠다.