[백준,c++] 12764번 - 싸지방에 간 준하

문제

12764번: 싸지방에 간 준하

 

코드

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    priority_queue<pair<int,int>,vector<pair<int,int>>, greater<>> min_heap;    // {끝나는 시간, 좌석번호}
    priority_queue<pair<int,int>,vector<pair<int,int>>, greater<>> seats;    // {좌석번호, 끝나는 시간}
    vector<pair<int,int>>time;
    vector<int>cnt(N);
    int ans = 0;
    
    for(int i=0; i<N; i++){
        int start, end; cin>>start>>end;
        time.push_back({start,end});
    }
    
    sort(time.begin(),time.end());
    int computer_num = 0;
    
    for(int i=0; i<N; i++){
        int start = time[i].first;
        int end = time[i].second;
        
        while(!min_heap.empty()){
            if(min_heap.top().first<start){
                seats.push({min_heap.top().second, min_heap.top().first});
                min_heap.pop();
            }
            else break;
        }
        
        if(seats.empty()){
            min_heap.push({end, ++computer_num});
            cnt[computer_num]++;
        }
        else{
            int seat = seats.top().first;
            min_heap.push({end, seat});
            cnt[seat]++;
            seats.pop();
        }
    }
    
    
    cout<<computer_num<<'\n';
    for(int i=1; i<=computer_num; i++){
        cout<<cnt[i]<<' ';
    }
}

 

풀이

11000번: 강의실 배정

처음에는 힙 하나로 위 문제와 비슷하다고 생각하여 하나의 힙으로 구현하였지만 "새로운 사람은 이전 사람이 이용하던 좌석이 아니라 비어있는 좌석 중에서 번호가 가장 작은 좌석에 앉아야 합니다."라는 조건 때문에 heap을 두 개를 사용하여 해결해야 합니다.

6
0 15
10 25
20 30
50 70
60 80
100 120

특히 위와 같은 입력일 때를 생각하여 고민하면 조금 더 조건에 부합하게 고민할 수 있습니다.

min_heap과 seats를 각각 최소 힙으로 {끝나는 시간, 좌석번호}, {좌석번호, 끝나는 시간}으로 저장한 뒤 빈 좌석들은 전부 seats로 옮겨서 비교하는 식으로 해결했습니다.