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

 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

 

 

 

---

- 문제

 

회의실을 예약하는 시작 시간과 끝나는 시간이 주어지면, 가장 많은 사람들이 회의실을 사용할 수 있는 경우를 구하는 문제다.

 

 

 

---

- 해설

 

저장을 할때 <시작시간,끝나는시간>으로 풀려고하면 진짜 힘들어지는 것 같다.

 

다른 사람들이 올린 질문에 답변 달린 힌트를 봤는데, <끝나는시간, 시작시간>으로 풀어보라고 해서 그렇게 했다가 바로 풀렸다.

 

<end, start>로 저장을 하면

이걸 정렬할 시에 

 

start 순서는 상관없이 end가 짧은것부터 저장이 됩니다.

 

그러면 이제 같은 end 중에서 어떤 start를 사용해도 상관이 없고(이전 end보다 더 작지만 않으면)

 

이걸 반복해서 문제를 풀 수 있다.

 

---

 

- 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int N, start, end, time, count = 0;
    vector<pair<int, int>> table;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> start >> end;
        table.push_back(pair<int, int>(end, start)); // 끝나는 시간부터 넣어서, 나중에 정렬할 때 끝나는 시간 순으로 정렬하도록
    }
    sort(table.begin(), table.end());
    time = table[0].first;
    count++;
    for (int i = 1; i <= N; i++)
    {
        if (table[i].second >= time) // 다음 시작시간이 끝나는 시간과 같거나 더 크면
        {
            time = table[i].first;
            count++;
        }
    }
    cout << count;

    return 0;
}