[LeetCode] 1942. The Number of the Smallest Unoccupied Chair

https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair/description/?envType=daily-question&envId=2024-10-11

leetcode - The Number of the Smallest Unoccupied Chair

문제 유형: 정렬, 우선순위 큐

문제 난이도: Medium

 

문제

There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.

• For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.

Return the chair number that the friend numbered targetFriend will sit on.

 

n명의 친구들이 0 ~ n-1의 번호로 매겨져서 파티에 참석합니다.

무한한 의자가 있습니다.

친구가 오면, 사용중이지 않은 가장 작은 숫자의 의자에 앉습니다.

즉, 0, 1, 5가 사용중인데 친구가 오면, 2번에 앉을 겁니다.

친구가 떠나면 그 자리에 앉을 수 있습니다.

 

2차원 배열 times를 받는데, times[i] = [arrival_i, leaving_i]가 있으면, i번째 친구가 arrival에 와서 leaving에 떠난다는 의미입니다.

정수 targetFriend가 주어집니다. 이 친구가 앉을 의자번호를 구하시오.

모든 도착 시간은 중복되지 않습니다.

 

 

풀이

우선순위 큐를 만들어서, 나갈시간과 의자번호를 나갈시간 기준 최소 힙으로 저장한다.

또, 의자번호를 최소힙으로 저장한다.

입장 시간이 중복이 없으므로, 우선 도착시간을 추출해놓는다.

 

그리고, times를 입장시간 기준으로 오름차순 정렬한다.  

times를 순차적으로 읽으면서, 우선 현재 입장시간보다 작은 나갈시간들을 담은 요소들을 최소 힙에서 빼서 그 의자번호들을 의자번호들을 저장하는 최소힙에 저장한다.

즉, 이번 친구가 오기 전, 또는 올 때 나가야되는 사람들을 보내고, 의자들을 돌려받는다.

만약 의자번호를 담은 우선순위 큐가 비어있지 않다면, 거기서 하나 빼서 할당하고, 나가는 우선순위 큐에 담는다.

비어있다면, 새로운 최대 번호를 갱신해서 할당하고, 나가는 우선순위큐에 담는다.

만약 이번 시간이 targetFriend의 입장시간이라면, 루프를 멈추고 ans를 반환한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

struct comp{
    bool operator()(const auto &a, const auto &b) {
        return a[1] > b[1];
    }
};

class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        int n = times.size();
        priority_queue<vector<int>, vector<vector<int>>, comp> outGoing; //{chariNo., end}
        priority_queue<int, vector<int>, greater<int>> nextSeats; // {charirNo.}

        int targetTime = times[targetFriend][0];
        sort(times.begin(), times.end());
        int maxChairNo = 0;
        int ans = 0;

        for(int i = 0; i < n; ++i) {
            int starts = times[i][0];
            int ends = times[i][1];
            while(!outGoing.empty() && starts >= outGoing.top()[1]) {
                nextSeats.push(outGoing.top()[0]);
                outGoing.pop();
            }

            int seat;
            if(!nextSeats.empty()) {
                seat = nextSeats.top();
                nextSeats.pop();
            } else {
                seat = maxChairNo++;
            }
            if(starts == targetTime) {
                ans = seat;
                break;
            }
            outGoing.push({seat, ends});
        }
        return ans;
    }
};