회의실 배정 1931

문제

접근 방법

생각하다 보니 프로그래머스에서 풀었던 단속카메라가 생각났다.
차이점은 이 문제는 음수를 허용하지 않지만 2^31-1까지의 범위고 프로그래머스는 음수를 허용하지만 -30,000~30,000의 범위란 것이다.
똑같이 끝점을 확인해보며 최솟값으로 갱신해주고 끝점을 넘어가면 카운트해주는 방식으로 접근하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<pair<int, int>> v;
    int N, cnt = 1;
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        int start, end;
        cin >> start >> end;
        v.push_back({start, end});
    }
    sort(v.begin(), v.end());
    int end = INT_MAX;
    for (auto i : v)
    {
        if (i.first >= end)
        {
            end = i.second;
            ++cnt;
            continue;
        }
        if (i.second < end)
        {
            end = i.second;
        }
    }
    cout << cnt;
    return 0;
}

풀이

시작점과 끝점을 벡터에 집어넣어주고 정렬해주면 시작점이 낮은 순으로 정렬된다.
현재 끝점보다 시작점이 높을 시 회의가 겹치지 않았다는 뜻이므로 cnt를 1 더해준다.
만약 현재 끝점보다 더 짧은 끝점이 있다면 그 끝점을 사용하는 것이 더 많은 회의를 이어가는 데 유리하므로 갱신해준다.