[LeetCode] 2402. Meeting Rooms III

https://leetcode.com/problems/meeting-rooms-iii/

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Meeting Rooms III

문제 유형 : 우선순위 큐

문제 난이도 : Hard

 

문제

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.

Meetings are allocated to rooms in the following manner:

1. Each meeting will take place in the unused room with the lowest number.
2. If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
3. When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.

A half-closed interval [a, b) is the interval between a and b including a and not including b.

 

n개의 회의실이 있습니다.

당신은 meetings라는 2차원 배열을 받습니다. [시작시간, 종료시간)으로 되어 있습니다. 시작 시간은 서로 겹치지 않습니다.

다음의 매너를 지키면서 회의가 지켜져야 합니다.

1. 각 회의는 방의 숫자가 작은 곳을 우선으로 회의실을 사용합니다.
2. 사용 가능한 방이 없으면, 방이 생길 때 까지 기다립니다. 지연된 시간만큼 시작 시간과 종료 시간이 있습니다.
3. 방이 비면, 기존 시작 시간이 더 빠른 회의부터 시작합니다.

가장 많은 회의가 이루어진 방의 번호를 구하시오.

만약 여러 개라면, 가장 낮은 번호를 구하시오.

[a, b)는 a는 포함하지만, b는 포함하지 않음으로 의미합니다.

 

풀이

아래 솔루션의 도움을 받았습니다.

https://leetcode.com/problems/meeting-rooms-iii/solutions/4744315/beats-100-users-c-explained

LeetCode - The World's Leading Online Programming Learning Platform

 

 

두 개의 우선순위 큐를 만들어서 하나는 사용 가능한 방, 하나는 회의중인 방을 관리한다.

n짜리 배열을 만들어서 횟수를 저장한다.

meetings배열을 정렬하여 하나씩 확인한다.

각 미팅동안 사용 가능한 방을 찾아서, 있다면 미팅을 할당한다.

방이 없다면, 사용 가능한 방중에서 가장 빨리 나오는 시간과 방을 체킹하여, 할당한다.

 

코드

C++

class Solution {
public:
    int mostBooked(int n, vector<vector<int>> &meetings) {
        vector<int> ans(n, 0);
        priority_queue<int, vector<int>, greater<int>> available;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> busy;
        
        for (int i = 0; i < n; i++) {
            available.push(i);
        }
        
        sort(meetings.begin(), meetings.end());

        for (auto &&meeting : meetings) {
            int start = meeting[0], end = meeting[1];

            // 시간지난 회의실 비우기
            while (!busy.empty() && busy.top().first <= start) {
                available.push(busy.top().second);
                busy.pop();
            }

            // 만약 사용가능한 곳이 있다면
            if (!available.empty()) {
                int top = available.top();
                ans[top]++;
                available.pop();
                busy.push({end, top});
            // 없다면, 다음 빠지는곳에 미리 예약걸어놓기
            } else {
                auto top = busy.top();
                int end1 = top.first, index = top.second;

                ans[index]++;
                busy.pop();
                busy.push({top.first + end - start, index});
            }
        }

        return max_element(ans.begin(), ans.end()) - ans.begin();
    }
};