[BOJ/백준] 1931 (회의실 배정) C++

주제

그리디

아이디어

1. 종료시간 기준으로 오름차순 배열
2. 가장 먼저 끝나는 회의 기준, 겹치는 회의 다 삭제하기!

소스코드

시간초과

/*
boj1931.cpp
2021-01-08 정설희
회의실 배정
*/

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

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

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

    vector <pair<int, int>> vec;

    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int t1, t2; cin >> t1 >> t2;
        vec.push_back({ t1,t2 });
    }

    sort(vec.begin(), vec.end(),cmp);
    int cnt = 0;

    while (vec.size()) {
        cnt++;
        int idx = 0;
        int sz = vec.size();
        vector <pair<int, int>> tmpV;
        for (int i = 1; i < sz; i++) {
            if (vec[i].first >= vec[idx].second)
                tmpV.push_back(vec[i]);
        }
        vec = tmpV;
    }
    
    cout << cnt;
  
}

시간초과가 뜬다..

성공!

/*
boj1931.cpp
2021-01-08 정설희
회의실 배정
*/

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

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

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

    vector <pair<int, int>> vec;

    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int t1, t2; cin >> t1 >> t2;
        vec.push_back({ t1,t2 });
    }

    sort(vec.begin(), vec.end(),cmp);
    int cnt = 1;
    int now = vec[0].second;
    for (int i = 1; i < n; i++) {
        if (vec[i].first >= now) {
            cnt++;
            now = vec[i].second;
        }
    }
    
    cout << cnt;
  
}

훨씬 간단하다.. for문 한번만 돌면서 그 때 그 때 now를 바꿔준다!

배운점

vector 요소 삭제 : vec.erase(vec.begin()+i);

vec.erase(vec.begin()+i);

이렇게 하면 vec[i]를 삭제 할 수 있다. 그 뒤부터 index가 하나 씩 당겨진다.

for문 조건 속 변수 변하지 않게 조심!

이게 무슨말이냐 하면..

for (int i = 1; i < vec.size(); i++) {
            if (vec[i].first < vec[idx].second)
                vec.erase(vec.begin() + i);
        }

위와 같은 경우에, vec의 요소가 하나씩 줄어들면서 vector의 사이즈가 바뀐다 -> ERROR
그걸 방지하기 위해서

int sz = vec.size();
for (int i = 1; i < sz; i++) {
            if (vec[i].first < vec[idx].second)
                vec.erase(vec.begin() + i);
        }

이렇게 sz로 바꿔줬는데도, ERROR가 떴다.
그 이유는 vector의 요소들이 erase 되면서 더이상 vec[i] 가 vec[i]가 아니게된것..!
지워질 때 마다 그 뒤부터 idx 하나 씩 땡겨진다