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

1931. 회의실 배정

1931번: 회의실 배정

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

사실은... 생각하지 않고 풀어낸 문제이다... 왜냐하면

예제에서 끝나는 시간이 오름차순으로 정렬된 것을 보고...

 

1. 끝나는 시간을 오름차순으로 정렬한 다음에...
2. 방금 시간한 회의의 끝나는 시간보다
3. 크거나 같은 다른 회의 시작 시간을 찾는다.
4. 시작할 회의가 없을 때까지 1~2를 반복한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned long long int ulli;

int main()
{
    int len, answer = 0;
    ulli endTime = 0;
    // first => end Time, second => start Time
    // end Time을 주축으로 정렬할 것이기 때문에
    vector<pair<ulli, ulli>> times;

    cin >> len;

    for (int i = 0; i < len; i++)
    {
        ulli startTime, endTime;
        cin >> startTime;
        cin >> endTime;
        times.push_back({ endTime, startTime });
    }

    // endTime을 기준으로 정렬
    sort(times.begin(), times.end());

    for (int i = 0; i < len; i++)
    {
        // 회의가 끝나는 시간보다 같거나 늦을 때는 회의를 시작할 수 있다
        if (endTime <= times[i].second)
        {
            // 끝나는 시간 갱신
            endTime = times[i].first;
            answer++;
        }
    }

    cout << answer;
}

일단 코드의 가독성이 좀 꽝이다... 구조체를 만들고 연산자 정의까지 하기가 귀찮아서 pair을 썼는데... start Time이 pair의 second, end Time이 pair의 first이기 때문에...

 

제출할 때는 설마 맞을 거라 생각하지는 않았지만... 맞았다. 끝나는 시간 오름차순 정렬이 중요한 문제였던 것 같은데...

날로 먹은 것 같다는 생각이 들었다.

 

---

 

그렇다면 왜 끝나는 시간이 오름차순일까? 를 생각해서 죄책감을 덜기로 했다.

 

내 생각엔, 빠른 시작시간보다 빠른 끝나는 시간이 더 중요하기 때문이다.

만약 시작 시간이 오름차순이었다면, 끝나는 시간이 최댓값인데도 시작 시간과 계속 비교하며 최악의 경우 한 번의 회의밖에 하지 못한다.

그렇지만, 끝나는 시간이 오름차순이면 최대한 빨리 끝나는 것에 집중했기 때문에, 회의를 최대한 많이 돌릴 수 있다.

 

간단하지만, 유익한 문제였다.