[C++] 백준 1931번: 회의실 배정

문제

난이도 : 실버 1
백준 1931번 : 회의실 배정

코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<pair<int, int>> v;

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;
        v.push_back({ a, b });
    }

    sort(v.begin(), v.end());

    int start = v[0].first, end = v[0].second;
    int answer = 1;

    for (int i = 1; i < N; i++)
    {
        if (start < v[i].first && end > v[i].second) 
        {
            start = v[i].first; end = v[i].second;
        }
        else if (v[i].first >= end)
        {
            start = v[i].first; end = v[i].second;
            answer++;
        }
    }

    cout << answer;

    return 0;
}

풀이

내가 생각하기에 라인 스위핑 문제인 것 같다
저번 문제들과 비슷하게 pair<int, int> 벡터에 데이터를 입력 받고 회의실 시작 시간으로 오름차순 정렬했다
이번엔 우선순위 큐가 필요없을 것 같아 사용하지 않았고 start와 end라는 변수를 만들었다.
대충 start, end는 최근까지 회의실을 사용한 회의의 시작 시간과 종료 시간으로 이해하면 되겠다
처음 초기화할 때 v의 0번째 index값으로 초기화 해주고 이때 answer을 1로 해주었다.(어찌됐던 0번째 회의가 방을 쓰는 거니까)
우리는 회의의 수를 최대로 만들어야 하므로 만약 최근 회의가 현재 회의 시간을 포함한다면(ex. 0~6은 1~3을 포함하고 있다) 최근 회의 말고 현재 회의 시간을 새롭게 갱신한다
코드에서 첫 번째 if문이 포함한다면 작은 범위를 start, end로 다시 지정해준다
그리고 만약 end가 i번째 회의의 시작시간 이전이라면 최근 회의 시간과 겹치지 않다는 의미이기에 회의의 수를 하나 늘린다.
대충 이렇게 start와 end를 갱신시켜나가며 answer를 구했다. 반례를 잘 찾는 것도 중요하다!!

결과