Level 2. 호텔 대실

Level 2. 호텔 대실

 

 

겹치는 구간의 최댓값을 구하는 문제다.

 

가장 간단한 방법은 배열을 만들어 1씩 더한 후, 가장 큰 값을 고르는 것이다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int time_to_sec(string time)
{
    return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));
}

int solution(vector<vector<string>> book_time)
{
    int answer = 0;
    vector<int> v(time_to_sec("23:59") - time_to_sec("00:00"), 0);

    for (vector<string>& time : book_time)
    {
        auto first = v.begin() + time_to_sec(time[0]);
        auto last  = v.begin() + min(time_to_sec(time[1]) + 10, time_to_sec("23:59"));

        for (auto it = first; it != last; ++it)
            answer = max(answer, ++*it);
    }

    return answer;
}

 

우선순위 큐를 이용한 더 효율적인 방법이다.

 

시작 시간이 이른 사람부터 채워넣어야 하므로 우선 정렬한다.

 

우선순위 큐를 종료 시간을 저장하는 최소힙으로 구성하고, 가장 이른 종료 시간이 시작 시간 이전이면 방을 뺀다.

 

이런 문제를 풀 때는 시작 시간이나 종료 시간을 기준으로 정렬해 생각해보면 도움이 될 것 같다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

int time_to_sec(string time)
{
    return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));
}

int solution(vector<vector<string>> book_time)
{
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> prQue;

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

    for (vector<string>& time : book_time)
    {
        int start = time_to_sec(time[0]);
        int end   = time_to_sec(time[1]) + 10;

        while (!prQue.empty() && prQue.top() <= start)
            prQue.pop();

        prQue.push(end);

        answer = max(answer, int(prQue.size()));
    }

    return answer;
}