[LeetCode] 2402. Meeting Room III

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

링크

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

문제

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.

 

Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0. 

Example 2:

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1. 

 

Constraints:

• 1 <= n <= 100
• 1 <= meetings.length <= 105
• meetings[i].length == 2
• 0 <= starti < endi <= 5 * 105
• All the values of starti are unique.

문제 설명 및 요점

• \( 0 \sim n-1 \) 까지의 회의실이 있고, 비어있는 회의실을 순차적으로 사용한다.
• 사용 가능한 회의실이 없을 경우 회의가 딜레이된다.
• 가장 많은 회의가 열린 회의실을 찾는다.

풀이

#그리디 #힙 #시뮬레이션

• 효율적으로 시뮬레이션을 돌려야 하는 문제
• 사용 가능한 회의실을 체크하기 위해 최소힙 하나, 가장 빨리 끝나는 회의를 알기 위해 최소힙 하나를 사용한다.
  • 지속적인 최솟값 체크 => 힙
• 모든 미팅에 대해
  • 현재 미팅의 시작 시간 이전의 회의는 모두 종료시킨다.
  • 사용 가능한 방이 없다면 가장 빨리 끝나는 회의를 강제로 하나 종료시키고, 현재 미팅의 시작 시간을 보정한다.
  • 사용 가능한 회의실을 얻고(heappop), 현재 미팅을 시작한다.

코드

from heapq import heapify, heappush, heappop
from collections import Counter

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        availableRooms = [i for i in range(n)]
        heapify(availableRooms)
        cnt = Counter()
        meetingEnds = [] # (endtime, roomNumber)

        for start, end in meetings:
            while meetingEnds and meetingEnds[0][0] <= start:
                _, prevRoom = heappop(meetingEnds)
                heappush(availableRooms, prevRoom)
            if not availableRooms:
                prevEnd, prevRoom = heappop(meetingEnds)
                heappush(availableRooms, prevRoom)
                end += prevEnd - start
            currRoom = heappop(availableRooms)
            cnt[currRoom] += 1
            heappush(meetingEnds, (end, currRoom))
        return cnt.most_common()[0][0]