Leetcode 1942. The Number of the Smallest Unoccupied Chair

문제

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 ~ 무한 의 번호가 붙혀져 있다.
• 주어진 배열에는 친구가 들어오는 시간과 나가는 시간이 적혀있다.
• 들어온 친구는 남아있는 의자 중 가장 숫자가 적은 의자에 앉아있다.
• i번째 인덱스의 친구가 앉게 될 의자의 번호를 리턴하시오

---

예시

times = [[3,10],[1,5],[2,6]], targetFriend = 0

• 3에 도착, 10에 나가는 친구가 앉게 될 의자를 구해야 한다.

1. 먼저 1, 5 가 들어와 0번 의자를 차지
2. 그 다음 2, 6 이 들어와 1번 의자를 차지
3. 마지막으로 3, 10 은 2번 의자를 차지한다.

• 2가 정답

---

제한

• $n == times.length$
• $2 <= n <= 10^4$
• $times[i].length == 2$
• $1 <= arrival_i < leaving_i <= 10^5$
• $0 <= targetFriend <= n - 1$
• 모든 도착시간은 다르다.

---

풀이

• 2개의 min heap을 동시에 써야 한다.
• 하나는 남은 자리, 하나는 떠날 시간과 차지한 의자의 번호를 적어둔다.

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        targetTime = times[targetFriend]
		# 도착 시간으로 정렬한다.
        times.sort(key=lambda k: k[0])
		# 친구 수만큼의 의자를 준비한다
        seats = [i for i in range(len(times))]
		# (떠날시간, 의자) 를 관리할 heap
        leaving = []
        heapify(seats)

        for arrive, leave in times:
        	# targetFriend가 도착하면 루프를 중단한다
            if arrive >= targetTime[0]:
                break
			# 떠날 사람이 있는지 확인하고, 빈 의자를 다시 사용할 수 있도록 힙에 넣는다.
            while leaving and leaving[0][0] <= arrive:
                t = heappop(leaving)
                heappush(seats, t[1])
			# 도착한 사람이 의자를 차지한다.
            leftSeat = heappop(seats)
            heappush(leaving, (leave, leftSeat))
		# 이미 떠난 사람들의 의자를 다시 사용 가능하게 한다
        while leaving and leaving[0][0] <= targetTime[0]:
            t = heappop(leaving)
            heappush(seats, t[1])
		# targetFriend 가앉을 의자의 번호를 리턴한다.
        return heappop(seats)