호텔 대실

객실의 사용을 최소화 해야하는 문제를 풀어봤다. 분명 이런 비슷한 류의 문제를 풀어본 기억이 있는데 기억이 안나서 혼자서 좀 많이 생각했다. 내가 풀었던 방법은 가장 먼저 모든 시간을 분으로 만들어 주고 가장 빠른 시간부터 시작하도록 정렬해줬다.

이후에는 Map을 활용해서 끝나는 시간만 저장한 뒤에 각 loop 마다 Map을 뒤져서 10분전의 시간이 존재하는지를 찾았다. 첫번째 테스트 케이스 돌릴때는 실패 했는데 방의 시간이 연속적으로 이어져야 하는거라서 한번 이어진 방을 찾았으면 그 방은 다시 스캔 안하도록 해줘야했다.

개인적으로 마음에 들지는 않은 풀이 방법이라 priority-queue 를 사용해서 다시 풀어봤다. pq에서는 결국 가장 빠르게 끝나는 시간 부터 나올거라서 현재 시간보다 -10 시간인 방들을 계속 빼주면서 q의 남아있는 방 수만큼 answer 을 업데이트 해주면 된다!

v1

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

vector<int> convert_time(vector<string>& v){
    string start = v[0], end = v[1]; 
    int h1 = stoi(start.substr(0,2)) * 60; 
    int m1 = stoi(start.substr(3,2)); 
    
    int h2 = stoi(end.substr(0,2)) * 60; 
    int m2 = stoi(end.substr(3,2));
    
    return {h1 + m1, h2 + m2}; 
}

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    vector<vector<int>> time_line; 
    map<int,int> timeMap; 
    for(vector<string>& v : book_time){
        time_line.push_back(convert_time(v)); 
    }
    
    sort(time_line.begin(), time_line.end(), [](vector<int>& a, vector<int>& b){
        return a < b; 
    }); 
    
    bool flag = true; 
    for(vector<int>& v : time_line){
        int target = v[0] - 10; 
        for(auto& it : timeMap){ //만약 퇴실 시간이 맞다면
            if(it.first <= target && timeMap[it.first] > 0){
                flag = false;
                timeMap[it.first]--; 
                break; 
            }
        }
        if(flag){
            answer++; 
        }
        timeMap[v[1]]++; 
        flag = true; 
    }
    
    
    return answer;
}

v2

```c
#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

int solution(vector<vector<string>> book_time) {
    int answer = 0;
    priority_queue<int,vector<int>,greater<int>> pq; 
    sort(book_time.begin(), book_time.end()); 
    for(vector<string>& v : book_time){
        string start_t = v[0], end_t = v[1]; 
        int nStart_t = stoi(start_t.substr(0,2)) * 60 + stoi(start_t.substr(3)); 
        int nEnd_t = stoi(end_t.substr(0,2)) * 60 + stoi(end_t.substr(3)); 
        
        while(!pq.empty() && pq.top() <= nStart_t - 10){
            pq.pop(); 
        }
        pq.push(nEnd_t); 
        answer = max(answer, (int)pq.size()); 
    }
    return answer;
}